塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-55二叉树的深度-python

《剑指offer》python实现系列,全目录

题目一:

二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

第一想法:

计算每条路径的长度,选择其中最大的

剑指offer方法:

递归

如果一棵树只有一个节点,那么它的深度为1.

如果根节点只有左子树而没有右子树,那么树的深度应该是其左子树的深度加1:

如果根节点只有右子树而没有左子树,那么树的深度应该是其右子树的深度加1

如果既有右子树又有左子树,那么该树的深度就是其左、右子树深度的较大值再加1.

1
2
3
4
5
6
7
8
class Solution:
def TreeDepth(self, pRoot):
if pRoot is None:
return 0
leftdepth = self.TreeDepth(pRoot.left)
rightdepth = self.TreeDepth(pRoot.right)

return max(leftdepth,rightdepth) + 1

题目二:

平衡二叉树

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

如果某二叉树中任意节点的左、右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

剑指offer方法一:

遍历每个结点,计算左右子树的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def IsBalanced(self, pRoot):
if pRoot is None:
return True

leftdepth = self.TreeDepth(pRoot.left)
rightdepth = self.TreeDepth(pRoot.right)
if abs(leftdepth-rightdepth) > 1:
return False
return self.IsBalanced(pRoot.left) and self.IsBalanced(pRoot.right)

def TreeDepth(self, pRoot):
#返回当前节点的深度
if pRoot is None:
return 0
leftdepth = self.TreeDepth(pRoot.left)
rightdepth = self.TreeDepth(pRoot.right)

return max(leftdepth,rightdepth) + 1

剑指offer方法二:

方法一的问题在于,自顶向下计算每个结点的深度,底层节点会被遍历很多次,

计算1的左子树深度时,depth(1.L)-> depth(2.L) -> depth(4.L)

计算2的左子树深度时,depth(2.L)-> depth(4.L)

因为1的左右子树深度之差不超过1不代表2的左右子树深度不超过1,所以要计算每个子树的深度

自底向上遍历,如果子树是平衡二叉树,则返回子树的高度;如果发现子树不是平衡二叉树,则直接停止遍历,这样至多只对每个结点访问一次。

检查每个子树是否是平衡的,若4是平衡的,5是平衡的,则2就是平衡的。

检查1的左子树深度时,dfs(1.L)-> dfs(2.L) -> dfs(4.L)

如果1的左右子树是平衡的,那么2的左右子树一定是平衡的(因为是先2平衡向上得到1平衡的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def IsBalanced_Solution(self, pRoot):
return self.check(pRoot) != -1

def check(self, pRoot):
#-1表示不平衡
if pRoot is None:
return 0
leftdepth = self.check(pRoot.left)
if leftdepth == -1: #若子树不平衡,直接return -1,返回上一层
return -1
rightdepth = self.check(pRoot.right)
if rightdepth == -1:
return -1
if abs(leftdepth-rightdepth) > 1:
return -1

return max(leftdepth,rightdepth) + 1
if help:小手一抖点个广告 or 大手一挥资助一下