[数据结构与算法]剑指offer java day18 搜索与回溯算法

T1 55 - I. 二叉树的深度

DFS 根节点的深度=max(左叶子深度，右叶子深度)+1

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

BFS

class Solution {
    public int maxDepth(TreeNode root) {
        if(root ==null) return 0;
        int res=0;
        List<TreeNode> queue = new LinkedList<>(){{add(root);}},tmp;
        while(!queue.isEmpty()){
            tmp = new LinkedList<TreeNode>();
            for(TreeNode node:queue){
                if(node.left!=null) tmp.add(node.left); //加入叶子节点
                if(node.right!=null)tmp.add(node.right);
            }
            res++;
            queue = tmp;
        }
        return res;
    }
}

T2 55 - II. 平衡二叉树

后序遍历 + 剪枝 从底至顶

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }
    //树的深度和是否平衡
    public int recur(TreeNode root){
        if(root == null) return 0;
         //左
        int left = recur(root.left);
        if(left == -1) return -1;//左叶子不平衡
        //右
        int right = recur(root.right); 
        if(right == -1) return -1;//右叶子不平衡
        //根
        //两叶子的深度差值(绝对值) 绝对值小于2平衡 并得到当前叶子对应根的深度
        return Math.abs(left-right)<2 ? Math.max(left,right)+1 :-1;
    }
}