剑指 Offer 55 – II. 平衡二叉树

题目描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true 。

示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false 。

限制：
0 <= 树的结点个数 <= 10000
链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/

解题思路

本题要求二叉树的深度，涉及使用递归的方式求二叉树深度，求二叉树深度的代码为：

// 求二叉树深度
func GetTreeDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    var depth, ld, rd int
    ld = GetTreeDepth(root.Left)
    rd = GetTreeDepth(root.Right)
    // 判断当前是左子树更高还是右子树更高,返回较高的那个高度+1
    if ld > rd {
        depth = ld + 1
    } else if ld <= rd {
        depth = rd + 1
    }
    return depth
}

或者将代码稍微变换一下，得到另一种求深度的方式：

// 求二叉树深度
func GetTreeDepth(root *TreeNode) int {
    var depth, ld, rd int
    // 这样不用判断node是不是nil了，因为根本进不去空结点
    if root.Left != nil {
        ld = GetTreeDepth(root.Left)
    }
    if root.Right != nil {
        rd = GetTreeDepth(root.Right)
    }
    // 判断当前是左子树更高还是右子树更高,返回较高的那个高度+1
    if ld > rd {
        depth = ld + 1
    } else if ld <= rd {
        depth = rd + 1
    }
    return depth
}

我们要在求深度的基础上判断是否平衡，因此只需要在判断哪个子树更高之前，判断两个子树的深度差是否超过1，并把判断的结果存在一个名为Result的指针里面。
原因：在遍历过程中，只要有一次深度差超过1，Result指向的值就会发生变化。因此只要变化了就说明不平衡。

解题代码

Golang

// 用求深度的方式递归,顺便判断是不是平衡,并返回结果
func GetResult(root *TreeNode, result *bool) int {
    if root == nil {
        return 0
    }
    var depth, ld, rd int
    ld = GetResult(root.Left, result)
    rd = GetResult(root.Right, result)
    if ld > rd+1 || ld < rd-1 {
        *result = false
    }
    if ld > rd {
        depth = ld + 1
    } else if ld <= rd {
        depth = rd + 1
    }
    return depth
}

// 判断是不是平衡二叉树
func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    result := true
    GetResult(root, &result)
    return result
}

Python

class Solution:
    def dfs(self, node):
        if not node:
            return 0
        ld = self.dfs(node.left)
        rd = self.dfs(node.right)
        if abs(ld - rd) > 1:
            self.res = False
        return max(ld, rd) + 1

    def isBalanced(self, root: TreeNode) -> bool:
        self.res = True
        self.dfs(root)
        return self.res

执行结果

Golang
执行结果：通过
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.9 MB, 在所有 Go 提交中击败了89.50%的用户
Python
执行结果：通过
执行用时：68 ms, 在所有 Python3 提交中击败了44.89%的用户
内存消耗：18.5 MB, 在所有 Python3 提交中击败了97.26%的用户

注意点

• 后序遍历，叶子节点那里dfs函数的返回值为0（因为只有根节点的时候高度是0），不是叶子节点则深度+1
• 用一个self.res记录是否平衡的结果
• ld = self.dfs(node.left) rd = self.dfs(node.right)
• 如果abs(ld - rd) > 1则改变self.res