题解 | #平衡二叉树#

平衡二叉树

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 root

2. 普通二叉树
在左右子树中查找是否存在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