Recursive Depth First Search Algorithm to Compute the Diameter o

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

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

推荐阅读：
我好困好困|小学作文　 看图写话 知错就改 刘赛柏|小学作文　 [组图]打雪仗|小学作文　 看图写话 我最爱吃的水果 戴海鑫|小学作文　 “六一”儿童节_550字　 2019年父亲节_1000字　 传统节日作文 快乐的”五一节”_400字　 n你和孩子说话的语气，决定了孩子的智商和情商　 有多大的手，端多大的碗　 有个知心的人， 就是幸福！　
评论列表
添加评论