面试题39:二叉树的深度

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

二叉树节点定义如下:

BinaryTreeNode
1
2
3
4
5
6
7
8
{
int value;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int data=int())
:value(data),left(NULL),right(NULL)
{}
}


分析

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

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

代码如下:

Depth(BinaryTreeNode* root)
1
2
3
4
5
6
7
{
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三个节点。这样导致时间复杂度较高。

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

代码如下:

_IsBalanced(BinaryTreeNode* root,int& depth)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
{
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上:点我前往(题目一)  点我前往(题目二)

<div>来自为知笔记(Wiz)</div>