本文共 23461 字，大约阅读时间需要 78 分钟。
剑指offer中有关树的题目汇总
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。
输入： 前序遍历[1,2,4,7,3,5,6,8],中序遍历[4,7,2,1,5,3,8,6]
输出：二叉树
思路
代码
#################面试题7########################重建二叉树class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): # write code here rootval = pre[0] root = TreeNode(rootval) for i in range(len(tin)): if rootval == tin[i]: leftpre = pre[1:i+1] lefttin = tin[0:i] rightpre = pre[i+1:len(pre)] righttin = tin[i+1:len(tin)] if leftpre != []: root.left = self.reConstructBinaryTree(leftpre, lefttin) else: root.left = None if rightpre != []: root.right = self.reConstructBinaryTree(rightpre, righttin) else: root.right = None return root
测试
################测试1##################功能测试class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nones = Solution()pre = [1,2,3,4,5,6,7]tin = [3,2,4,1,6,5,7]pre = [1,2,4,7,3,5,6,8]tin = [4,7,2,1,5,3,8,6]root = s.reConstructBinaryTree(pre, tin)
给定义一颗二叉树和其中一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右节点的指针，还有一个指向父节点的指针
思路
代码【未完成】
#################面试题8########################二叉树的下一节
测试
################测试#################
输入两颗二叉树A，B，判断B是不是A的子结构。
思路
1）在树A和树B中找到根节点值一样的结构
2）判断A中以R为根节点的子树是不是包含树B一样的子树
代码
#################面试题26########################树的子结构class Solution: def HasSubtree(self,pRoot1,pRoot2): result = False if pRoot1 != None and pRoot2 != None: if pRoot1.val == pRoot2.val: result = self.DoesTree1HasTree2(pRoot1,pRoot2) if not result: result = self.HasSubtree(pRoot1.left,pRoot2) if not result: result = self.HasSubtree(pRoot1.right,pRoot2) return result def DoesTree1HasTree2(self,pRoot1,pRoot2): if pRoot2 == None: return True if pRoot1 == None: return False if pRoot1.val != pRoot2.val: return False return self.DoesTree1HasTree2(pRoot1.left,pRoot2.left) and\ self.DoesTree1HasTree2(pRoot1.right,pRoot2.right)
测试
################测试##################先定义二叉树类class BinaryTreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonedef printAllNode(pHead): if pHead == None: return None p = pHead key = p.val if p.left: leftnode = printAllNode(p.left) else: leftnode = None if p.right: rightnode = printAllNode(p.right) else: rightnode = None treedic = {key:[leftnode,rightnode]} return treedic###########测试1###################树A和树B为普通二叉树pRoot1 = BinaryTreeNode(8)p1 = pRoot1#建立一个链表p2 = BinaryTreeNode(8)p3 = BinaryTreeNode(9)p4 = BinaryTreeNode(2)p5 = BinaryTreeNode(5)p1.right = p2p2.right = p3p3.right = p4p4.right = p5printAllNode(p1)pRoot2 = BinaryTreeNode(8)p21 = pRoot2#建立一个链表p22 = BinaryTreeNode(9)p23 = BinaryTreeNode(3)p24 = BinaryTreeNode(2)p21.right = p22p22.left = p23p22.right = p24printAllNode(pRoot2)s = Solution()s.HasSubtree(pRoot1,pRoot2)###########测试2###################两个二叉树中有一个根节点为NonepRoot1 = NonepRoot2 = BinaryTreeNode(2)p21 = pRoot2#建立一个链表p22 = BinaryTreeNode(4)p23 = BinaryTreeNode(6)p24 = BinaryTreeNode(7)p21.left = p22p22.left = p23p22.right = p24printAllNode(pRoot2)s = Solution()s.HasSubtree(pRoot2,pRoot1)###########测试3###################两棵树无左右节点pRoot1 = BinaryTreeNode(3)pRoot2 = BinaryTreeNode(2)s = Solution()s.HasSubtree(pRoot1,pRoot2) 请完成一个函数，输入一颗二叉树，该函数输出它的镜像
思路
代码
#################面试题27########################二叉树的镜像class Solution: def MirrorRecursively(self,pNode): if pNode == None: return None if pNode.left == None and pNode.right == None: return pNode pNode.left,pNode.right = pNode.right,pNode.left if pNode.left != None: pNode.left = self.MirrorRecursively(pNode.left) if pNode.right != None: pNode.right = self.MirrorRecursively(pNode.right) return pNode
测试
################测试##################先定义二叉树类class BinaryTreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonedef printAllNode(pHead): if pHead == None: return None p = pHead key = p.val if p.left: leftnode = printAllNode(p.left) else: leftnode = None if p.right: rightnode = printAllNode(p.right) else: rightnode = None treedic = {key:[leftnode,rightnode]} return treedic###########测试1###################树A和树B为普通二叉树pRoot1 = BinaryTreeNode(6)p1 = pRoot1#建立一个链表p2 = BinaryTreeNode(8)p3 = BinaryTreeNode(9)p4 = BinaryTreeNode(2)p5 = BinaryTreeNode(5)p1.right = p2p2.right = p3p3.right = p4p4.right = p5printAllNode(pRoot1)s = Solution()MirrorRoot = s.MirrorRecursively(pRoot1)printAllNode(MirrorRoot)###########测试2###################只有一个节点的二叉树pRoot1 = BinaryTreeNode(6)printAllNode(pRoot1)s = Solution()MirrorRoot = s.MirrorRecursively(pRoot1)printAllNode(MirrorRoot)###########测试2###################根节点为NonepRoot1 =printAllNode(pRoot1)s = Solution()MirrorRoot = s.MirrorRecursively(pRoot1)printAllNode(MirrorRoot) 请实现一个函数，用来判断一颗二叉树是不是对称的。如果一颗二叉树和它的镜像一样那么它是对称的
思路
通过比较二叉树的前序遍历和对称前序遍历来判断二叉树是不是对称的
代码
#################面试题28########################对称的二叉树class Solution: def isSymmetrical(self,pRoot): pRoot1 = pRoot pRoot2 = pRoot def isSymmetrical(pRoot1,pRoot2): if pRoot1 == None and pRoot2 == None: return True if pRoot1 == None or pRoot2 == None: return False if pRoot1.val != pRoot2.val: return False return isSymmetrical(pRoot1.right,pRoot2.left) and isSymmetrical(pRoot1.left,pRoot2.right) return isSymmetrical(pRoot1,pRoot2)
测试
################测试##################先定义二叉树类class BinaryTreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonedef printAllNode(pHead): if pHead == None: return None p = pHead key = p.val if p.left: leftnode = printAllNode(p.left) else: leftnode = None if p.right: rightnode = printAllNode(p.right) else: rightnode = None treedic = {key:[leftnode,rightnode]} return treedic###########测试1###################对称的二叉树pRoot1 = BinaryTreeNode(1)p1 = pRoot1#建立一个链表p2 = BinaryTreeNode(2)p3 = BinaryTreeNode(2)p4 = BinaryTreeNode(3)p5 = BinaryTreeNode(3)p1.right = p2p1.left = p3p2.right = p4p3.left = p5printAllNode(pRoot1)s = Solution()s.isSymmetrical(pRoot1)###########测试2###################因结构而不对称的二叉树pRoot1 = BinaryTreeNode(1)p1 = pRoot1#建立一个链表p2 = BinaryTreeNode(2)p3 = BinaryTreeNode(2)p4 = BinaryTreeNode(3)p5 = BinaryTreeNode(3)p1.right = p2p1.right = p3p2.right = p4p3.left = p5printAllNode(pRoot1)s = Solution()s.isSymmetrical(pRoot1)###########测试3###################结构对称但节点的值不对称的二叉树pRoot1 = BinaryTreeNode(1)p1 = pRoot1#建立一个链表p2 = BinaryTreeNode(3)p3 = BinaryTreeNode(4)p4 = BinaryTreeNode(3)p5 = BinaryTreeNode(3)p1.right = p2p1.left = p3p2.right = p4p3.left = p5printAllNode(pRoot1)s = Solution()s.isSymmetrical(pRoot1)###########测试4###################根节点为None的二叉树pRoot1 = Nones = Solution()s.isSymmetrical(pRoot1)###########测试4###################只有一个节点的二叉树pRoot1 = BinaryTreeNode(1)s = Solution()s.isSymmetrical(pRoot1)###########测试4###################所有节点的值都相同的二叉树pRoot1 = BinaryTreeNode(1)p1 = pRoot1#建立一个链表p2 = BinaryTreeNode(1)p3 = BinaryTreeNode(1)p4 = BinaryTreeNode(1)p5 = BinaryTreeNode(1)p1.right = p2p1.right = p3p2.right = p4p3.left = p5printAllNode(pRoot1)s = Solution()s.isSymmetrical(pRoot1) 从上到下打印二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
思路
运用队列最终结果返回一个列表
代码
#################面试题32########################不分行从上到下打印二叉树class Solution: # 返回从上到下每个节点值列表，例：[1,2,3] def PrintFromTopToBottom(self, root): if not root: return [] queue = [root] result = [] while queue != []: node = queue.pop(0) result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result
测试
################测试#################class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None####测试1#########完全二叉树node1 = TreeNode(8)node1 = TreeNode(8)node2 = TreeNode(6)node3 = TreeNode(10)node4 = TreeNode(5)node5 = TreeNode(7)node6 = TreeNode(9)node7 = TreeNode(11)node1.left = node2node1.right = node3node2.left = node4node2.right = node5node3.left = node6#node3.right = node7root = node1s = Solution()s.PrintFromTopToBottom(root)####测试2#########所有节点只有左子树#node1 = TreeNode(8)node2 = TreeNode(6)node3 = TreeNode(10)node4 = TreeNode(5)node5 = TreeNode(7)node6 = TreeNode(9)node7 = TreeNode(11)node1.left = node2node2.left = node4node4.left = node6#node3.right = node7root = node1s = Solution()s.PrintFromTopToBottom(root)#return 8 6 5 9####测试3#########所有节点只有右子树node1 = TreeNode(8)node2 = TreeNode(6)node4 = TreeNode(5)node6 = TreeNode(9)node1.right = node2node2.right = node4node4.right = node6root = node1s = Solution()s.PrintFromTopToBottom(root)#return 8 6 5 9####测试4#########根节点为Nones = Solution()s.PrintFromTopToBottom(None) #return []####测试5#########只有一个节点的二叉树node1 = TreeNode(8)s = Solution()s.PrintFromTopToBottom(node1) #return
从上到下按层打印二叉树的每个节点，同一层的节点按照从左到右的顺序打印。每一层打印一行
思路
运用队列最终结果返回一个列表 还需要两个变量存储当前层还没打印的节点数，以及下一层的节点数目
代码
#################面试题32########################分行从上到下打印二叉树class Solution: # 返回从上到下每个节点值列表，例：[1,2,3] def PrintFromTopToBottom(self, root): if not root: return [] queue = [root] result = [] toBePrinted = 1 nextLevel = 0 while queue != []: node = queue.pop(0) toBePrinted -= 1 result.append(node.val) if node.left: queue.append(node.left) nextLevel += 1 if node.right: queue.append(node.right) nextLevel += 1 if toBePrinted == 0: print(result) result = [] toBePrinted = nextLevel nextLevel = 0
测试
################测试#################class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None####测试1#########完全二叉树node1 = TreeNode(8)node1 = TreeNode(8)node2 = TreeNode(6)node3 = TreeNode(10)node4 = TreeNode(5)node5 = TreeNode(7)node6 = TreeNode(9)node7 = TreeNode(11)node1.left = node2node1.right = node3node2.left = node4node2.right = node5node3.left = node6#node3.right = node7root = node1s = Solution()s.PrintFromTopToBottom(root)####测试2#########所有节点只有左子树#node1 = TreeNode(8)node2 = TreeNode(6)node3 = TreeNode(10)node4 = TreeNode(5)node5 = TreeNode(7)node6 = TreeNode(9)node7 = TreeNode(11)node1.left = node2node2.left = node4node4.left = node6#node3.right = node7root = node1s = Solution()s.PrintFromTopToBottom(root)#return 8 6 5 9####测试3#########所有节点只有右子树node1 = TreeNode(8)node2 = TreeNode(6)node4 = TreeNode(5)node6 = TreeNode(9)node1.right = node2node2.right = node4node4.right = node6root = node1s = Solution()s.PrintFromTopToBottom(root)#return 8 6 5 9####测试4#########根节点为Nones = Solution()s.PrintFromTopToBottom(None) #return []####测试5#########只有一个节点的二叉树node1 = TreeNode(8)s = Solution()s.PrintFromTopToBottom(node1) #return
第一行按照从左到右的顺序，第二行按照从右到左的顺序，依次类推，每一层打印一行
思路
需要用到两个栈
代码
#################面试题32########################之字形打印二叉树class Solution: # 返回从上到下每个节点值列表，例：[1,2,3] def PrintFromTopToBottom(self, root): if not root: return [] stack1 = [root] stack2 = [] result = [] toBePrinted = 1 nextLevel = 0 isOdd = 1 while stack2 != [] or stack1 != [] : if isOdd == 1: while stack1 != []: node = stack1.pop() toBePrinted -= 1 result.append(node.val) if node.left: stack2.append(node.left) nextLevel += 1 if node.right: stack2.append(node.right) nextLevel += 1 else: while stack2 !=[]: node = stack2.pop() toBePrinted -= 1 result.append(node.val) if node.right: stack1.append(node.right) nextLevel += 1 if node.left: stack1.append(node.left) nextLevel += 1 if toBePrinted == 0: print(result) result = [] isOdd = not isOdd toBePrinted = nextLevel nextLevel = 0
测试
################测试#################class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None####测试1#########完全二叉树node1 = TreeNode(1)node2 = TreeNode(2)node3 = TreeNode(3)node4 = TreeNode(4)node5 = TreeNode(5)node6 = TreeNode(6)node7 = TreeNode(7)node8 = TreeNode(8)node9 = TreeNode(9)node10 = TreeNode(10)node11 = TreeNode(11)node12 = TreeNode(12)node13 = TreeNode(13)node14 = TreeNode(14)node15 = TreeNode(15)node1.left = node2node1.right = node3node2.left = node4node2.right = node5node3.left = node6node3.right = node7node4.left = node8node4.right = node9node5.left = node10node5.right = node11node6.left = node12node6.right = node13node7.left = node14node7.right = node15root = node1s = Solution()s.PrintFromTopToBottom(root)####测试2#########所有节点只有左子树#node1 = TreeNode(8)node2 = TreeNode(6)node4 = TreeNode(5)node6 = TreeNode(9)node1.left = node2node2.left = node4node4.left = node6root = node1s = Solution()s.PrintFromTopToBottom(root)####测试3#########所有节点只有右子树node1 = TreeNode(8)node2 = TreeNode(6)node4 = TreeNode(5)node6 = TreeNode(9)node1.right = node2node2.right = node4node4.right = node6root = node1s = Solution()s.PrintFromTopToBottom(root)#return 8 6 5 9####测试4#########根节点为Nones = Solution()s.PrintFromTopToBottom(None) #return []####测试5#########只有一个节点的二叉树node1 = TreeNode(8)s = Solution()s.PrintFromTopToBottom(node1) #return
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果，如果是则返回true，不是返回false。假设输入的数组的任意两个数字都互不相同。
思路
二叉搜索树：若左子树不空，则左子树上所有节点的值都小于根节点
若右子树不空，则右子树上所有节点的值都大于根节点
左右子树均是二叉搜索树
代码
#################面试题33########################二叉搜索树的后序遍历序列class Solution: def VerifySquenceOfBST(self, sequence): if not sequence: return seqOflen =len(sequence) if seqOflen == 2: return True if seqOflen == 1: return True root = sequence[seqOflen-1] i = 0 while i < seqOflen - 1 and sequence[i] < root: i += 1 leftseq = sequence[0:i] j = i while j < seqOflen - 1: if sequence[j] > root: j += 1 else: return False rightseq = sequence[i:seqOflen - 1] if leftseq == [] and rightseq != []: return self.VerifySquenceOfBST(rightseq) elif leftseq != [] and rightseq == []: return self.VerifySquenceOfBST(leftseq) else: return self.VerifySquenceOfBST(leftseq) and self.VerifySquenceOfBST(rightseq)
测试
################测试#################sequence = [5,7,6,9,11,10,8]s = Solution()s.VerifySquenceOfBST(sequence) #return Truesequence = [7,4,6,5]s = Solution()s.VerifySquenceOfBST(sequence) #return Truesequence = [7]s = Solution()s.VerifySquenceOfBST(sequence) #return Truesequence = [5,4,3,2,1]s = Solution()s.VerifySquenceOfBST(sequence) #return True
输入一颗二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径
思路
前序遍历，利用栈
代码
#################面试题34########################二叉树中和为某一值的路径class Solution: # 返回二维列表，内部每个列表表示找到的路径 def FindPath(self, root, expectNumber): # write code here if not root: return [] if root and not root.left and not root.right and root.val == expectNumber: return [[root.val]] result = [] left = self.FindPath(root.left,expectNumber - root.val) right = self.FindPath(root.right,expectNumber - root.val) for i in left + right: result.append([root.val] + i) return result
测试
################测试#################class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonenode1 = TreeNode(10)node2 = TreeNode(5)node3 = TreeNode(12)node4 = TreeNode(4)node5 = TreeNode(7)node1.left = node2node1.right = node3node2.left = node4node2.right = node5root = node1s = Solution()expectNumber = 22s.FindPath(root,22)
输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
思路
中序遍历
先指向左子节点的指针调整为链表指向前一个节点的指针，
原先指向右子节点的指针调整为链表中指向后一个节点的指针
第一步：中序遍历，则要查找到中序遍历的第一个节点，也就是最下最左边的子结点pHeadOfList
代码【未实现】
#################面试题36########################二叉树与双向链表
测试
################测试#################
实现两个函数，分别用来序列化和反序列化二叉树
思路
反序列化未完成
代码
#################面试题37########################二叉树与双向链表def Serialize(pRoot): stream = [] if pRoot == None: stream.append('$') return stream stream.append(pRoot.val) stream.extend(Serialize(pRoot.left)) stream.extend(Serialize(pRoot.right)) return stream 测试
################测试#################class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None############测试1################3#输入的二叉树是完全二叉树node1 = TreeNode(1)node2 = TreeNode(2)node3 = TreeNode(3)node4 = TreeNode(4)node5 = TreeNode(5)node6 = TreeNode(6)node1.left = node2node1.right = node3node2.left = node4node3.left = node5node3.right = node6pRoot = node1stream = Serialize(pRoot)for i in range(len(stream)-1): print(stream[i],end =',')print(stream[len(stream)-1])############测试2################3#所有的节点都没有左子树node1 = TreeNode(1)node2 = TreeNode(2)node3 = TreeNode(3)node4 = TreeNode(4)node5 = TreeNode(5)node6 = TreeNode(6)node1.left = node2node2.left = node4node3.left = node5pRoot = node1stream = Serialize(pRoot)for i in range(len(stream)-1): print(stream[i],end =',')print(stream[len(stream)-1])############测试3################3#只有一个节点的二叉树node1 = TreeNode(1)pRoot = node1stream = Serialize(pRoot)for i in range(len(stream)-1): print(stream[i],end =',')print(stream[len(stream)-1])############测试4################3#节点为Nonestream = Serialize(None)for i in range(len(stream)-1): print(stream[i],end =',')print(stream[len(stream)-1])
给定一颗二叉搜索树，请找出其中第k大的节点。
思路
先中后序遍历：
代码
#################面试题54########################二叉搜索树的第K大节点class Solution: # 返回对应节点TreeNode def KthNode(self, pRoot, k): # write code here if not pRoot: return None order = self.inOrder(pRoot) if k <= 0 or k > len(order): return None #return order[k-1].val return order[k-1] #返回的是节点 def inOrder(self,pRoot): #采用递归结构 btree = [] def recurse(Node): if Node: recurse(Node.left) btree.append(Node) recurse(Node.right) recurse(pRoot) return btree
测试
################测试#################class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None#功能测试Node1 = TreeNode(5)Node2 = TreeNode(3)Node3 = TreeNode(7)Node4 = TreeNode(2)Node5 = TreeNode(4)Node6 = TreeNode(6)Node7 = TreeNode(8)Node1.left = Node2Node1.right = Node3Node2.left = Node4Node2.right = Node5Node3.left = Node6Node3.right = Node7pRoot = Node1k = 3s=Solution()s.KthNode(pRoot,k)#边界值测试# k=0 或 k = 1 或 k=二叉搜索树的节点数 或 k = 二叉搜索树的节点数 + 1Node1 = TreeNode(8)Node2 = TreeNode(6)Node3 = TreeNode(10)Node4 = TreeNode(5)Node5 = TreeNode(7)Node6 = TreeNode(9)Node7 = TreeNode(11)Node1.left = Node2Node1.right = Node3Node2.left = Node4Node2.right = Node5Node3.left = Node6Node3.right = Node7pRoot = Node1s=Solution()s.KthNode(pRoot,0)s.KthNode(pRoot,1)s.KthNode(pRoot,7)s.KthNode(pRoot,8)#特殊值测试s=Solution()s.KthNode(None,k)
输入一颗二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点，成树的一条路径，最长路径的长度为树的深度
思路
代码
#################面试题55########################二叉树的深度class Solution: def TreeDepth(self, pRoot): # write code here if not pRoot: return 0 nleft = self.TreeDepth(pRoot.left) nright = self.TreeDepth(pRoot.right) return max(nleft,nright) + 1
测试
################测试#################class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None#功能测试# 普通的二叉树Node1 = TreeNode(5)Node2 = TreeNode(3)Node3 = TreeNode(7)Node4 = TreeNode(2)Node5 = TreeNode(4)Node6 = TreeNode(6)Node7 = TreeNode(8)Node1.left = Node2Node1.right = Node3Node2.left = Node4Node2.right = Node5Node3.left = Node6Node3.right = Node7pRoot = Node1s=Solution()s.TreeDepth(pRoot)# 仅有左子树Node1 = TreeNode(5)Node2 = TreeNode(3)Node3 = TreeNode(7)Node4 = TreeNode(2)Node5 = TreeNode(4)Node6 = TreeNode(6)Node7 = TreeNode(8)Node1.left = Node2Node2.left = Node4Node3.left = Node6pRoot = Node1s=Solution()s.TreeDepth(pRoot)#特殊输入测试#只有一个节点Node1 = TreeNode(5)pRoot = Node1s=Solution()s.TreeDepth(pRoot)#头节点为Nones=Solution()s.TreeDepth(None)
输入一颗二叉树的根节点，判断该树是不是平衡二叉树，如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一颗平衡二叉树
思路
后序遍历
代码
#################面试题55########################二叉树的深度class Solution: def IfBalanced(self, pRoot): if not pRoot: pDepth = 0 return True ifbalence,pDepth = self.BalancedAndDepth(pRoot) return ifbalence def BalancedAndDepth(self, pRoot): if not pRoot: pDepth = 0 return True,pDepth pDepth = 1 ifbalence = False ifleftbalanced,nleft = self.BalancedAndDepth(pRoot.left) ifrightbalanced,nright = self.BalancedAndDepth(pRoot.right) if ifleftbalanced and ifrightbalanced: diff = nleft - nright if diff <= 1 and diff >= -1: pDepth = max(nleft,nright) + 1 ifbalence = True return ifbalence,pDepth
测试
################测试#################class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None#功能测试# 平衡二叉树Node1 = TreeNode(5)Node2 = TreeNode(3)Node3 = TreeNode(7)Node4 = TreeNode(2)Node5 = TreeNode(4)Node6 = TreeNode(6)Node7 = TreeNode(8)Node1.left = Node2Node1.right = Node3Node2.left = Node4Node2.right = Node5Node3.left = Node6Node3.right = Node7pRoot = Node1s=Solution()s.IfBalanced(pRoot) # 非平衡二叉树Node1 = TreeNode(5)Node2 = TreeNode(3)Node3 = TreeNode(7)Node4 = TreeNode(2)Node5 = TreeNode(4)Node6 = TreeNode(6)Node7 = TreeNode(8)Node1.left = Node2Node2.left = Node4Node3.left = Node6pRoot = Node1s=Solution()s.IfBalanced(pRoot) #特殊输入测试#二叉树中只有一个节点Node1 = TreeNode(5)pRoot = Node1s=Solution()s.IfBalanced(pRoot) #头结点为Nones.IfBalanced(None)
转载地址：http://pcusn.baihongyu.com/