11.24打卡

1. 相同的树（100）

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null)
            return true;

        if(p==null||q==null)
            return  false;

        if(p.val != q.val)   
            return false;

        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

2. 对称二叉树（101）

给你一个二叉树的根节点 root ， 检查它是否轴对称。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
       if(root==null||(root.left==null&&root.right==null))
            return true;
        TreeNode left=root.left;
        TreeNode right = root.right;
        return is_symmetric( left, right);
    }

    private boolean is_symmetric(TreeNode left, TreeNode right) {
        if(left==null && right==null){
            return true;
        }
        if(left==null||right==null){
            return false;
        }
        if(left.val!=right.val)
            return false;
        return is_symmetric(left.left,right.right)&&is_symmetric(left.right,right.left);
    }
}

3. 二叉树的层次遍历（102）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
         Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res =new ArrayList<>();
        if(root!=null)
            queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> temp =  new ArrayList<>();
            for (int i = queue.size(); i >0 ; i--) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left !=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
            }
            res.add(temp);
        }
        return res;
    }
}

4. 二叉树锯齿形层次（103）

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res =new ArrayList<>();
        if(root!=null)
            queue.add(root);
        while (!queue.isEmpty()){
            LinkedList<Integer> temp =  new LinkedList<>();
            for (int i = queue.size(); i >0 ; i--) {
                TreeNode node = queue.poll();
                if(res.size() %2==0)
                    temp.addLast(node.val);
                else  temp.addFirst(node.val);
                if(node.left !=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
            }
            res.add(temp);
        }
        return res;
    }
}

5. 二叉树的最大深度（104）

给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
         if(root==null) return 0;
        if(root.left==null&&root.right==null)
            return 1;
        return Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1);
  
    }
}

6. 从前序、中序构造二叉树（105）

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
 
    private Map<Integer,Integer> map;
    private  int[] preorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder =preorder;
        map =  new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return dfsbuild(0,preorder.length-1,0);
        
    }

    private TreeNode dfsbuild(int prestart, int preend , int instart) {
        if(prestart>preend)
            return null;
        int rootval = preorder[prestart];
        int inid=map.get(rootval);
        TreeNode root = new TreeNode(rootval);
        int leftnum = inid-instart;
        root.left=dfsbuild(prestart+1,prestart+leftnum,instart);
        root.right=dfsbuild(prestart+leftnum+1,preend,inid+1);
        return root;
    }
}