剑指offer - 平衡二叉树(Java实现)

题目链接：https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&&tqId=11192&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：首先判断当前这个树是否满足平衡二叉树条件：左右子树高度差不大于 1，如果满足分别判断其左右子树是否为平衡二叉树，如果最后树为空，则满足平衡二叉树的条件，则作为递归出口。

import java.util.*;

public class Solution {
    Map<TreeNode, Integer> map = new HashMap<>();
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null) return true;
        return Math.abs(Depth(root.left) - Depth(root.right)) <= 1
            && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    public int Depth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(Depth(root.left), Depth(root.right)) + 1;
    }
}

  思路二：首先我们求出所有子树的高度，然后逐一的判断每一颗子树是否为平衡二叉树。

import java.util.*;

public class Solution {
    Map<TreeNode, Integer> map = new HashMap<>();
    public boolean IsBalanced_Solution(TreeNode root) {
        Depth(root); //预先处理每一颗树的高度
        return Judge(root);
    }
    public boolean Judge(TreeNode root) {
        if(root == null) return true; 
        return Math.abs(map.get(root.left) - map.get(root.right)) <= 1 
            && Judge(root.left) && Judge(root.right);
    }
    public int Depth(TreeNode root) {
        if(root == null) {
            map.put(root, 0);
            return 0;
        }
        if(map.get(root) != null) return map.get(root);
        map.put(root, Math.max(Depth(root.left), Depth(root.right)) + 1);
        return map.get(root);
    }
}