C#LeetCode刷题之#110-平衡二叉树（Balanced Binary Tree）

问题

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

给定二叉树 [3,9,20,null,null,15,7]

3

/ \

9 20

/ \

15 7

返回 true 。

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

1

/ \

2 2

/ \

3 3

/ \

4 4

返回 false 。

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Given the following tree [3,9,20,null,null,15,7]:

3

/ \

9 20

/ \

15 7

Return true.

Given the following tree [1,2,2,3,3,null,null,4,4]:

1

/ \

2 2

/ \

3 3

/ \

4 4

Return false.

示例

public class Program {

    public static void Main(string[] args) {

        var root = new TreeNode(1) {

            left = new TreeNode(2),

            right = new TreeNode(3)

        };

        var res = IsBalanced(root);

        Console.WriteLine(res);

        root = new TreeNode(1) {

            left = new TreeNode(2) {

                left = new TreeNode(3) {

                    left = new TreeNode(4)

                }

            },

            right = new TreeNode(5) {

                right = new TreeNode(6)

            }

        };

        res = IsBalanced2(root);

        Console.WriteLine(res);

        Console.ReadKey();

    }

    public static bool IsBalanced(TreeNode root) {

        //传统递归法，简单易写

        //空树是平衡二叉树，因为左右子树数量都是 0

        if(root == null) return true;

        //左右子树高度差大于 1，不是平衡二叉树

        if(Math.Abs(MaxDepth(root.left) - MaxDepth(root.right)) > 1) return false;

        //判定左右子树是否为平衡二叉树

        return IsBalanced(root.left) && IsBalanced(root.right);

    }

    public static int MaxDepth(TreeNode root) {

        //计算树每个子树的高度

        if(root == null) return 0;

        var left = MaxDepth(root.left);

        var right = MaxDepth(root.right);

        return Math.Max(left, right) + 1;

    }

    public static bool IsBalanced2(TreeNode root) {

        //优化递归法

        //此段代码引用自 LeetCode 的提交代码

        //由本人添加注释

        return MaxDepth2(root) >= 0;

    }

    public static int MaxDepth2(TreeNode root) {

        //如果是空树，判定为平衡的

        if(root == null) return 0;

        //计算左右子树的高度

        var left = MaxDepth2(root.left);

        var right = MaxDepth2(root.right);

        //如果左子树、右子树或高度差大于 1，则返回 -1

        //-1 表示判定为非平衡树，立即返回

        //导致调用堆栈在回溯时发现上一次是 -1

        //由于代码 left < 0 || right < 0 的存在，会使 -1 逐步上传

        //又被回溯到上上一次，一直到无法回溯时为止

        //按照原代码作者的部分注释，即不平衡的树会被传染到最上层

        //也即当发现一个 -1 时，该代码以非常高的效率判定原树为非平衡的

        //因为当前树为平衡的，不能判定原树是不是平衡的

        //但当前树为非平衡的，原树肯定是不平衡的

        //感谢原作者的代码为我们分享如此巧妙的优化

        if(left < 0 || right < 0 || Math.Abs(left - right) > 1) return -1;

        return Math.Max(left, right) + 1;

    }

    public class TreeNode {

        public int val;

        public TreeNode left;

        public TreeNode right;

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

    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

True

False

分析：

显而易见，以上2种算法的时间复杂度均为： $O(n)$ 。

巴特西

C#LeetCode刷题之#110-平衡二叉树（Balanced Binary Tree）

最新文章

热门文章