题解 | #平衡二叉树#
平衡二叉树
http://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
【剑指offer】平衡二叉树（python）
递归返回当前结点是否平衡，和当前深度。
class Solution: def IsBalanced_Solution(self, pRoot): # write code here def dfs(root): if root is None: return True,0 lf, ld = dfs(root.left) rf, rd = dfs(root.right) return lf and rf and abs(ld-rd)<=1, max(ld,rd)+1 flag,_ = dfs(pRoot) return flag这样逻辑更清晰一点，使用嵌套函数dfs得到深度，然后再比较。
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def IsBalanced_Solution(self, pRoot): # write code here def dfs(root): if root == None: return 0 return 1 + max(dfs(root.left), dfs(root.right)) if pRoot is None: return True if abs(dfs(pRoot.left) - dfs(pRoot.right)) > 1: return False else: return True
相关题：树中两个结点的最低公共祖先
1. 二叉搜索树
二叉搜索树的特殊性质，root.val >= p.val && root.val <= q.val
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if root is None: return root if root.val > p.val and root.val > q.val: return self.lowestCommonAncestor(root.left, p, q) if root.val < p.val and root.val < q.val: return self.lowestCommonAncestor(root.right, p, q) return root2. 普通二叉树
在左右子树中查找是否存在p或者q，如果p或者q分别在两个子树中，那么说明根节点就是最低公共祖先。
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if (root is None) or (root == p) or (root == q): return root left = self.lowestCommonAncestor(root.left,p,q) right = self.lowestCommonAncestor(root.right,p,q) if left is None: return right elif right is None: return left else: return root
