[剑指 Offer 第 2 版第 55_2 题] “平衡二叉树”做题记录

第 55-2 题：平衡二叉树

传送门：平衡二叉树，牛客网 online judge 地址。

输入一棵二叉树的根结点，判断该树是不是平衡二叉树。

如果某二叉树中任意结点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。

注意：

• 规定空树也是一棵平衡二叉树。

样例：

输入：二叉树 [5,7,11,null,null,12,9,null,null,null,null] 如下所示， 5 / \ 7 11 / \ 12 9 输出：true

思路：深度优先遍历（后序遍历）。

Python 代码：

  # 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):
        # 全局变量
        flag = 1

        def isBalanced(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """

            if root is None:
                return True
            self.__dfs(root)
            return self.flag

        def __dfs(self, node):
            """
            返回以 root 为根的二叉树的高度，如果左右子树其中之一不是 AVL ，则返回 -1
            :param node:
            :return:
            """
            if node is None:
                return 0
            left = self.__dfs(node.left)
            right = self.__dfs(node.right)

            if abs(left - right) > 1:
                self.flag = 0
                # 这里不能写 return
            return max(left, right) + 1

Java 代码：

  class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // 第 55 题：二叉树的深度（判断是不是平衡二叉树）
    // 可以提交到 LeetCode 第 110 题的测试用例
    // 参考资料1：
    // https://blog.csdn.net/derrantcm/article/details/46771529
    public class Solution {

        public boolean isBalanced(TreeNode root) {
            if (root == null) {
                return true;
            }
            int[] depth = new int[1];
            depth[0] = 0;
            return postOrder(root, depth);
        }

        // 后序遍历
        private boolean postOrder(TreeNode node, int[] depth) {
            if (node == null) {
                depth[0] = 0;
                return true;
            }
            int[] left = new int[1];
            int[] right = new int[1];
            // 如果左子树和右子树都不是平衡二叉树，直接就走到最后，返回 false
            if (postOrder(node.left, left) && postOrder(node.right, right)) {
                int diff = left[0] - right[0];
                if (diff <= 1 && diff >= -1) {
                    depth[0] = Integer.max(left[0], right[0]) + 1;
                    return true;
                }
            }
            return false;
        }
    }

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/