543 二叉树的直径
对于根节点r,它的直径无非有三种可能:左子树的直径,右子树的直径,已经左右子树高度之和。所以后序遍历整棵树,然后得到这三个值,最后返回最大值就可以。因为c++不能返回多个值,所以我设置了一个全局变量栈,来存放左右子树的高度。
进一步简化问题,发现两棵子树的直径,归根到底还是某左右子树高度之和,而我们所需要的,也无非就是一个最大值,所以可以设置一个全局变量存放它,每次如果当前节点的左右子树高度之和比它大,就更新。
/**
* 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 max_diam = 0;
int dep(TreeNode *root){
if(!root) return 0;
int left_h = dep(root -> left);
int right_h = dep(root -> right);
if(left_h + right_h > max_diam)
max_diam = left_h + right_h;
int h = left_h > right_h ? left_h + 1 : right_h + 1;
return h;
}
int diameterOfBinaryTree(TreeNode* root) {
int h = dep(root);
return max_diam;
}
};
网友评论