Recursive Depth First Search Algorithm to Compute the Diameter o

  • 时间：2020-09-10 12:55:33
  • 分类：网络文摘
  • 阅读：140 次

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

          1
         / \
        2   3
       / \     
      4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Compute the Diameter of a Binary Tree using Recursive Depth First Search Algorithm

The diameter can be computed as the depth of the left subtree plus the depth of the right subtree. However, as the diameter may not go through the root, it may exist in sub problems i.e. left or right tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, dfs(root)));
    }
    
private:
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        return depth(root->left) + depth(root->right);  
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(depth(root->left), depth(root->right)) + 1;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, dfs(root)));
    }
    
private:
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        return depth(root->left) + depth(root->right);  
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(depth(root->left), depth(root->right)) + 1;
    }
};

The following is a shorter implementation that gets rid of a intermediate DFS function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, depth(root->left) +depth(root->>right)));
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + max(depth(root->left), depth(root->right));
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, depth(root->left) +depth(root->>right)));
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + max(depth(root->left), depth(root->right));
    }
};

The C++ Depth First Search Algorithm is implemented using Recursion. We’ve noticed that the depth function is called many times for a same Tree Node, thus we can use a hash map to store the values for the visited nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, depth(root->left) + depth(root->right)));
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        if (data.find(root) != data.end()) return data[root];
        int r = 1 + max(depth(root->left), depth(root->right));
        data[root] = r;
        return r;
    }
 
private:
    unordered_map<TreeNode*, int> data;    
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = diameterOfBinaryTree(root->left);
        int right = diameterOfBinaryTree(root->right);
        return max(left, max(right, depth(root->left) + depth(root->right)));
    }
    
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        if (data.find(root) != data.end()) return data[root];
        int r = 1 + max(depth(root->left), depth(root->right));
        data[root] = r;
        return r;
    }

private:
    unordered_map<TreeNode*, int> data;    
};

However, the above Recursive DFS is not optimal as we may visit a node more than once. We can compute the diameter on the fly when we compute the depth of the binary tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        depth(root);
        return ans;
    }
    
    int depth(TreeNode* root) {
        if (!root) return 0;
        int L = depth(root->left);
        int R = depth(root->right);
        ans = max(ans, L + R);
        return max(L, R) + 1;
    }
 
private:
    int ans;
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        depth(root);
        return ans;
    }
    
    int depth(TreeNode* root) {
        if (!root) return 0;
        int L = depth(root->left);
        int R = depth(root->right);
        ans = max(ans, L + R);
        return max(L, R) + 1;
    }

private:
    int ans;
};

And the time complexity is O(N) where N is the number of the nodes in the binary tree. The space requirement is also O(N) due to implicit usage from Recursive calls.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
闭门羹　 比上帝还挑剔的人　 无理数的由来　 数学王国的巾帼英雄　 从死亡线上生还的人　 一个永恒运动的世界　 卡尔丹诺公式的由来　 面积相等时哪种平面图形周长最大　 小强下了几盘棋——比赛中的推理问题（一）　 名次如何排列　
评论列表
添加评论