二叉树-快速复习

• • 翻转二叉树
  • 5、最大二叉树
  • 二叉树的最大深度
  • 合并二叉树
  • 单值二叉树
  • 叶子相似的树
  • 左叶子之和

翻转二叉树（简单）
先序就是自上而下的翻转
后序就是自下而上的翻转
都可以，但是不能中序！

// 将整棵树的节点翻转
TreeNode invertTree(TreeNode root) {
    // base case
    if (root == null) {
        return null;
    }

    
    // root 节点需要交换它的左右子节点
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // 让左右子节点继续翻转它们的子节点
    invertTree(root.left);
    invertTree(root.right);

    return root;
}

最大二叉树

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums,0,nums.length-1);

    }

    private TreeNode dfs(int[] nums,  int left, int right) {

        if(left>right) //不是left>=right
            return null;


        int max=Integer.MIN_VALUE;
        int idx=-1;
        for (int i = left; i <= right; i++) {//i∈[left,right]
            if(max 
二叉树的最大深度 
添加链接描述
 最大深入用dfs，最小深度用bfs。
 
class Solution {
    int maxDepth=-1;
    public int maxDepth(TreeNode root) {
        dfs(root,0);
        return maxDepth;
    }

    private void dfs(TreeNode root, int curDept) {
        if(root==null){
            maxDepth=Math.max(maxDepth,curDept);
            return;
        }

        dfs(root.left,curDept+1);
        dfs(root.right,curDept+1);
    }
}
 
合并二叉树 
添加链接描述
 不需要重新建树，复用两棵树其一即可。
 
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if(t2==null) return t1;
    if(t1==null) return t2;
    t1.val+=t2.val;
    t1.left=mergeTrees(t1.left,t2.left);
    t1.right=mergeTrees(t1.right,t2.right);
    return t1;
    }
}
 
单值二叉树 
添加链接描述
 
class Solution {
    int t;
    public boolean isUnivalTree(TreeNode root) {
        if(root==null)
            return true;
        t=root.val;
        return dfs(root.left) && dfs(root.right);
    }

    private boolean dfs(TreeNode node) {
        if(node==null)
            return true;

        if(node.val!=t)
            return false;

        return dfs(node.left) && dfs(node.right);
    }
}
 
叶子相似的树 
添加链接描述
 就朴素的记录两个然后比较，优化不好理解。
 
class Solution {
    List list1=new ArrayList<>();
    List list2=new ArrayList<>();
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        dfs(root1,list1);
        dfs(root2,list2);
        int idx=0;
        if(list2.size()!=list1.size()){
            return false;
        }
        return list1.equals(list2);
    }

    private void dfs(TreeNode root, List list) {
        if(root==null){
            return;
        }
        if(root.left==null && root.right==null){
            list.add(root.val);
        }
        dfs(root.left,list);
        dfs(root.right,list);
    }
}
 
左叶子之和 
添加链接描述
 
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return root != null ? dfs(root) : 0;
    }

    public int dfs(TreeNode node) {
        int ans = 0;
        if (node.left != null) {
            ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
        }
        if (node.right != null && !isLeafNode(node.right)) {
            ans += dfs(node.right);
        }
        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }
}