平衡二叉树

Question

这段代码有一些问题，例如多次检查、length返回值和更改其他变量。但我暂时无法想象如何让它变得更好，或者如果这是可能的话。将其转换为基于堆栈的解决方案似乎有点过于复杂了。

请提供对此代码的回顾，如果可能的话，您认为在可读性和性能或可能出现的问题方面有哪些可以改进的地方。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    boolean isBalanced = true;

    public boolean isBalanced(TreeNode root) {
        length(root);
        return isBalanced;
    }

    public int length(TreeNode a) {
        if (a == null) {
            return 0;
        }
        if (isBalanced == false) {
            return 0;
        }
        int x = length(a.left);
        if (isBalanced == false) {
            return 0;
        }
        int y = length(a.right);
        if (isBalanced == false) {
            return 0;
        }
        if (Math.abs(x - y) > 1) {
            isBalanced = false;
            return 0;
        }
        return Math.max(x, y) + 1;
    }
}

对于这个问题，高度平衡二叉树被定义为一个二叉树，其中每个节点的两个子树的深度不超过1。

Answer 1

真正伤害这段代码的是，length方法希望同时返回两件事:分支深度和全局isBalanced状态。

为此，作者直接返回分支深度，isBalanced作为全局变量。我完全反对全局变量，但我必须承认这是可行的。不过，我认为有一行没用的代码：

public int length(TreeNode a) {
    if (a == null) {
        return 0;
    }
    if (isBalanced == false) { // <-- Useless
        return 0;              // <-- Useless
    }                          // <-- Useless

不然的话，也不算太糟。它使用一个神奇的值来早期从递归返回。

另一种可能是抛出一个UnbalancedException --不要马上杀了我，在重新处理异常情况时抛出异常并不是坏事！如果不经常发生这种情况，这是相当合理的，并使设计更加清洁：

public class Solution {
    public boolean isBalanced(TreeNode root) {
        try{
            length(root);
            return true;
        } catch(UnbalancedException unbalanced){
            return false;
        }
    }

    public int length(TreeNode a) throws UnbalancedException{
        if (a == null) {
            return 0;
        }
        int x = length(a.left);
        int y = length(a.right);
        if (Math.abs(x - y) > 1) {
            throw new UnbalancedException();
        }
        return Math.max(x, y) + 1;
    }
}

通过这个设计，您已经获得了一个实际工作的length方法！

最有可能的方法是创建一个像BalancedStatus这样的临时响应对象：

public class BalancedStatus {
     private final boolean isBalanced;
     private int depth;
     // Getters, and constructors here
}

以及：

public class Solution {
    public boolean isBalanced(TreeNode root) {
        BalancedStatus rootStatus = length(root);
        return rootStatus.isBalanced();
    }
    public BalancedStatus length(TreeNode a) {
        if (a == null) {
            return new BalancedStatus();
        }
        BalancedStatus x = length(a.left);
        if(!x.isBalanced()){
             return new BalancedStatus(false);
        }
        BalancedStatus y = length(a.right);
        if(!y.isBalanced()){
             return new BalancedStatus(false);
        }
        if (Math.abs(x - y) > 1) {
             return new BalancedStatus(false);
        }
        return new BalancedStatus(Math.max(x, y) + 1);
    }
}

但我不喜欢这样，因为它在每个递归级别实例化两个对象.

最后，我们可以减少递归并使用迭代，但是由于这是分支递归，我们需要一个List (Queue?)追踪进展情况。

优点：

• 没有递归(没有堆栈溢出等)
• 容易提前退出(只需return)

Cons:

• 需要设置节点的List才能完成
• 需要能够从节点链接回父节点(Map?)传播深度