剑指Offer55-II-平衡二叉树

剑指Offer55-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

来源:力扣(LeetCode)

链接:力扣

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一解

使用后序遍历,通过计算左右子树的高度,判断高度差是否大于 1 。

当递归到如下节点时:


left = 0

right = 0

return 1


left = 0

right = 0

return 1


left = 1

right = 1

return 2


left = 0

right = 0

return 1


left = 2

right = 1

return 3


left = 0

right = 0

return 1


left = 3

right = 1

return -1


# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def isBalanced(self, root: TreeNode) -> bool:

        def dfs(node):

            if not node: return 0

            left = dfs(node.left)

            # 进行剪枝

            if left == -1: return -1

            right = dfs(node.right)

            # 进行剪枝

            if right == -1: return -1

            # 返回树的高度

            return max(left, right) + 1 if abs(left - right) <= 1 else - 1

        return dfs(root) != -1