1

之前侄儿头条遇到过，翻过来竟然当时题目都没有读懂。

1.1 java

1.1.1 递归的判断实现

alt

1.1.2 空节点的判定

处理不好，浪费20分钟

    boolean judgeAVL(TreeNode root){
    //param checek
        if(root == null)
            return true;//这点容易错！

1.1.3 性能对比实践

c++ 10倍于java

alt

java版本的优化

就是附件2 附件3 java的比较

alt

2 code

  • 待消化的c++ ,来源官方题解
  • java 最简单版本
  • java 最复杂版本，尤其边界的处理，建议使用getordefault
  • java 中间版本，处理不好，容易空指针
class Solution {
public:
    map<TreeNode*, int> hs;
    int depth(TreeNode *root) {
        if (!root) return 0;
        if (hs.find(root) != hs.end()) return hs[root];
        int ldep = depth(root->left);
        int rdep = depth(root->right);
        return hs[root] = max(ldep, rdep) + 1;
    }
    bool judge(TreeNode *root) {
        if (!root) return true;
        return abs(hs[root->left] - hs[root->right]) <= 1 && 
        judge(root->left) && judge(root->right);
    }
    bool IsBalanced_Solution(TreeNode* root) {
        depth(root);
        return judge(root);
    }
};


public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return judgeAVL(root);
    }

        int GetTreeDepth(TreeNode root){
    if(root == null) return 0;

    int leftLen = GetTreeDepth(root.left);
    int rightLen = GetTreeDepth(root.right);

    return leftLen >=rightLen?(leftLen+1):(rightLen+1);
    }

    boolean judgeAVL(TreeNode root){
    //param checek
        if(root == null)
            return true;//容易错
        
    int LeftLen = GetTreeDepth(root.left);
    int RightLen = GetTreeDepth(root.right);
    
    int Diff = Math.abs( LeftLen - RightLen);
    
    return Diff <=1 && judgeAVL(root.left) && judgeAVL(root.right);

    // 这种实现方式存在同一个节点扫描两次开销
    }
}



//最复杂


import java.util.HashMap;
public class Solution {
    
    HashMap<TreeNode,Integer> treeDepthKV;
    public boolean IsBalanced_Solution(TreeNode root) {
        treeDepthKV = new HashMap<TreeNode,Integer>();
        
        treeDepthKV.put(null,0);//真的有这种边界case ! java
        GetTreeDepth(root);
        
        return judgeAVL(root);
    }

    int GetTreeDepth(TreeNode root){
    if(root == null) return 0;
    if(treeDepthKV.get(root)!=null)
        return treeDepthKV.get(root);

    int leftLen = GetTreeDepth(root.left);
    int rightLen = GetTreeDepth(root.right);

    int depth = Math.max(leftLen,rightLen)+1;
    //return leftLen >=rightLen?(leftLen+1):(rightLen+1);

    treeDepthKV.put(root,depth);

    return  depth; 

    }

    boolean judgeAVL(TreeNode root){
    //param checek
        if(root == null)
            return true;//这点容易错！
        
    //int LeftLen = GetTreeDepth(root.left);
    //int RightLen = GetTreeDepth(root.right);
    Integer LeftLen = treeDepthKV.get(root.left);
    Integer RightLen = treeDepthKV.get(root.right);
    
    int Diff = Math.abs( LeftLen - RightLen);
    
    return Diff <=1 && judgeAVL(root.left) && judgeAVL(root.right);

    // 这种实现方式存在同一个节点扫描两次开销
    }
}





import java.util.HashMap;
public class Solution {
    
    HashMap<TreeNode,Integer> treeDepthKV;
    public boolean IsBalanced_Solution(TreeNode root) {
        treeDepthKV = new HashMap<TreeNode,Integer>();
        return judgeAVL(root);
    }

    int GetTreeDepth(TreeNode root){
    if(root == null) return 0;
    if(treeDepthKV.get(root)!=null)
        return treeDepthKV.get(root);

    int leftLen = GetTreeDepth(root.left);
    int rightLen = GetTreeDepth(root.right);

    int depth = Math.max(leftLen,rightLen)+1;
    //return leftLen >=rightLen?(leftLen+1):(rightLen+1);

    treeDepthKV.put(root,depth);

    return  depth; 

    }

    boolean judgeAVL(TreeNode root){
    //param checek
        if(root == null)
            return true;//这点容易错！
        
    int LeftLen = GetTreeDepth(root.left);
    int RightLen = GetTreeDepth(root.right);
    //int LeftLen = treeDepthKV.get(root.left);
    //int RightLen = treeDepthKV.get(root.right);
    
    int Diff = Math.abs( LeftLen - RightLen);
    
    return Diff <=1 && judgeAVL(root.left) && judgeAVL(root.right);

    // 这种实现方式存在同一个节点扫描两次开销
    }
}