Recursive Depth First Search Algorithm to Compute the Diameter o

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

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) —

推荐阅读：
数正方形个数的数学题：5X5方格共有36个格点　 数学题：小兔晴天可以采12个蘑菇　 数学题：老师说我像你这么大的时候你才刚刚1岁　 数学题：甲、丙两组人比乙组人数多2倍还多2人　 数学题：22名家长和老师陪同学生参加某次数学竞赛　 数学题：求X的长度是多少厘米　 正好可以把它平均切成2个相等的正方体　 数学题：求三角形ABC中阴影正方形的边长是多少厘米　 数学题：三角形ABF的面积比三角形CEF的面积大8平方厘米　 数学题：这个式子是不是某个数的平方　
评论列表
添加评论