面试题39:二叉树的深度

题目一:输入一颗二叉树的根节点,求该树的深度。从根节点到叶节点一次经过的节点形成树的一条路径,最长路径的长度为树的深度。

二叉树节点定义如下:

```struct BinaryTreeNode { int value; BinaryTreeNode* left; BinaryTreeNode* right; BinaryTreeNode(int data=int()) :value(data),left(NULL),right(NULL) {} }


* * *

### 分析

此题可利用递归很方便的完成,步骤如下:

*   判断参数root是否为空?为空就返回0;
*   否则计算root的左右子树的高度;
*   比较左右子树高度,取较大者,返回较大的值加1(root自身占一层)。

代码如下:

```int Depth(BinaryTreeNode* root)
{
    if(root==NULL)
        return 0;
    int LeftDepth=Depth(root->left);
    int RightDepth=Depth(root->right);
    return LeftDepth>RightDepth?LeftDepth+1:RightDepth+1;
}

题目二:输入一颗二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意两个节点的左右子树的深度相差不超过1,那么它就是一颗平衡二叉树。


分析

最容易想到的就是遍历二叉树,每遍历到一个节点时,去求它的左右子树的深度并比较即可。然而这种方法需要将很多节点遍历多次。如下图:

求1的深度时,需要遍历剩下的所有节点。然后求2的深度时,需要遍历4和7两个节点。求3的深度时,又需要遍历5,6,8三个节点。这样导致时间复杂度较高。

有没有办法减少遍历节点的次数呢?答案是有的。那就是将每次遍历过的节点保存起来。我们可以将从根节点到叶节点所经过的所有节点看成一条路径。每次向下进入子树时,将当前节点保存进路径里面。从子树退回到父节点时,再将它从路径中删除。如此,我们便可以只遍历一次。求遍历过程中路径的最大值就可以,即最长路径。

代码如下:

```bool IsBalanced(BinaryTreeNode* root,int& depth) { if(root==NULL) { depth=0; return true; } int left,right; if(IsBalaced(root->left,left) && _IsBalanced(root->right,right) { int diff=right-left; if(diff>=-1 && diff <=1) { depth=left>right?left+1:right+1; return true; } } return false; }

bool IsBalanced(BinaryTreeNode* root) { int depth=0; return _IsBalanced(root,depth); } ```

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往(题目一)  点我前往(题目二)

[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")
来自为知笔记(Wiz)")