0. 总结

1. 层序遍历，从左到右。LinkedList，addLast，PollFirst。先左后右
2. 前序遍历，Stack，push，pop，add。先右后左
3. 中序遍历：Stack，先存入左子树，然后出栈，指向右子树
4. 后序遍历：Stack，push，pop，addFirst。先左后右
5. BST中序为递增，反中序为递减
6. 前序和中序重建、中序和后序重建

1. 前序遍历

1. 二叉树的前序遍历：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

   class Solution {
   public List<Integer> preorderTraversal(TreeNode root) {
       //前序：根左右
       //Stack、ArrayList
       //push，pop，add
       //先右后左
   
       Stack<TreeNode> stack = new Stack<>();
       List<Integer> list = new ArrayList<>();
       if(root == null){
           return list;
       }else{
           stack.push(root);
       }
   
       while(!stack.isEmpty()){
           TreeNode node = stack.pop();
           list.add(node.val);
           if(node.right != null){
               stack.push(node.right);
           }
           if(node.left != null){
               stack.push(node.left);
           }
       }
       return list;
   }
   }

2. 中序遍历

1. 二叉树中序遍历：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

   class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //中序：左根右
        //Stack、ArrayList
        //先存入左子树，然后接收弹出的左子树，添加左子树的val，然后指向右子树
   
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
   
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            //接收左子树
            root = stack.pop();
            //存入左子树的val
            list.add(root.val);
            //指向右子树
            root = root.right;
        }
        return list;
    }
   }

3. 后序遍历

1. 二叉树的后序遍历：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

   class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        //后序：左右根
        //Stack、LinkedList
        //push、pop、addFirst
        //先左后右
   
        Stack<TreeNode> stack = new Stack<>();
        LinkedList<Integer> list = new LinkedList<>();
        if(root == null){
            return list;
        }else{
            stack.push(root);
        }
   
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.addFirst(node.val);
            if(node.left != null){
                stack.push(node.left);
            }
            if(node.right != null){
                stack.push(node.right);
            }
        }
        return list;
    }
   }

4. 层序遍历

1. 二叉树的Z形遍历：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

   class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //层序遍历：Z字形
        //结果ArrayList、LinkedList、层存储LinkedList
        //addLast、pollFirst、奇数addFirst、偶数addLast
        //先左后右
   
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
   
        if(root == null){
            return result;
        }else{
            queue.addLast(root);
        }
   
        while(!queue.isEmpty()){
            LinkedList<Integer> list = new LinkedList<>();
            int size = result.size();
            int len = queue.size();
            for(int i=0;i<len;i++){
                TreeNode node = queue.pollFirst();
                if(size%2 == 0){
                    //偶数，addLast
                    list.addLast(node.val);
                }
                if(size%2 == 1){
                    //奇数，addFirst
                    list.addFirst(node.val);
                }
                if(node.left != null){
                    queue.addLast(node.left);
                }
                if(node.right != null){
                    queue.addLast(node.right);
                }
            }
            result.add(list);
        }
        return result;
    }
   }

2. 二叉树从上到下打印：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

3. 二叉树从下往上打印：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

5. BST相关：中序遍历为递增，反中序遍历为递减

1. BST中第k小的元素：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

2. BST转累加树：https://leetcode-cn.com/problems/convert-bst-to-greater-tree/

3. 有序数组转BST：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

4. 有序链表转BST：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

   class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        //链表转BST，快慢指针找中点，快走2慢走1，跳出循环后慢就是中点
        if(head == null){
            return null;
        }
        //null指针作为尾部
        return dfs(head,null);
    }
   
    public TreeNode dfs(ListNode head,ListNode tail){
        if(head == tail){
            return null;
        }
   
        ListNode fast = head;
        ListNode slow = head;
   
        while(fast != tail && fast.next != tail){
            fast = fast.next.next;
            slow = slow.next;
        }
   
        TreeNode root = new TreeNode(slow.val);
        root.left = dfs(head,slow);
        root.right = dfs(slow.next,tail);
   
        return root;
    }
   }

5. BST的最近公共祖先：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

   class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //类型：公共祖先节点
        //思路：递归左右子树，如果左为空，返回右，如果右为空，返回左
   
        if(root == null || root == p || root == q){
            return root;
        }
   
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
   
        if(left == null){
            return right;
        }
        if(right == null){
            return left;
        }
        return root;
    }
   }

6. 递归

1. 二叉树中最大路径和(随意节点出发)：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

   class Solution {
    //result取最大，初始为最小
    int result = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        //从任意节点出发，每次递归都要提取左右子树能够递归的最大深度，然后跟当前根节点值叠加
        if(root == null){
            return 0;
        }
   
        dfs(root);
        return result;
    }
   
    public int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
   
        //提取左右子树能够到达的最大深度
        int left = Math.max(0,dfs(root.left));
        int right = Math.max(0,dfs(root.right));
   
        result = Math.max(result,root.val+left+right);
        //返回当前根节点加上左右子树中深度大的
        return root.val + Math.max(left,right);
    }
   }

2. 路径总和组合——根节点：https://leetcode-cn.com/problems/path-sum-ii/

   class Solution {
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        //dfs前序递归，如果sum能够递减到0，添加list
        if(root == null){
            return result;
        }
        dfs(root,sum);
        return result;
    }
   
    public void dfs(TreeNode root,int sum){
        if(root == null){
            return;
        }
   
        sum -= root.val;
        list.add(root.val);
   
        if(sum == 0 && root.left == null && root.right == null){
            result.add(new ArrayList<>(list));
        }else{
            dfs(root.left,sum);
            dfs(root.right,sum);
        }
   
        //回溯
        list.remove(list.size()-1);
    }
   }

3. 判断路径：https://leetcode-cn.com/problems/path-sum/

   class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        //sum能够递减到0并且到达树的底部
        if(root == null){
            return false;
        }
        sum -= root.val;
        if(sum == 0 && root.left == null && root.right == null){
            return true;
        }else{
            return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
        }
    }
   }

4. 树的子结构：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/

   class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //B在A的左右子树中，并且节点值要相同
   
        if(A == null || B == null){
            return false;
        }
        return isSubStructure(A.left,B) || isSubStructure(A.right,B) || compare(A,B);
    }
   
    public boolean compare(TreeNode A,TreeNode B){
        if(B == null){
            return true;
        }
        if(A == null || B == null || A.val != B.val){
            return false;
        }
        //A和B的左右子树比较
        return compare(A.left,B.left) && compare(A.right,B.right);
    }
   }

5. 二叉树的右视图：https://leetcode-cn.com/problems/binary-tree-right-side-view/

   class Solution {
    int cur = 0;
    List<Integer> result = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        //右视图，递归右子树直到底部，用一个层数控制变量来控制存入
        if(root == null){
            return result;
        }
        dfs(root,0);
        return result;
    }
   
    public void dfs(TreeNode root,int depth){
        if(root == null){
            return;
        }
        if(cur == depth){
            result.add(root.val);
            cur++;
        }
        //右视图，先右后左
        dfs(root.right,depth+1);
        dfs(root.left,depth+1);
    }
   }

6. 二叉树的最小深度：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

   class Solution {
    public int minDepth(TreeNode root) {
        //最小深度，取左右子树递归的最小值
        if(root == null){
            return 0;
        }
   
        //如果左子树为空右子树不为空，返回右子树递归的结果+1
        if(root.left == null && root.right != null){
            return minDepth(root.right)+1;
        }
   
        //同理
        if(root.left != null && root.right == null){
            return minDepth(root.left)+1;
        }
   
        //返回最小值+1
        return Math.min(minDepth(root.left),minDepth(root.right))+1;
    }
   }

7. 二叉树的直径：https://leetcode-cn.com/problems/diameter-of-binary-tree/

   class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        //左子树深度 + 右子树深度
        if(root == null){
            return 0;
        }
   
        dfs(root);
        return max;
    }
   
    public int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        if(left + right > max){
            max = left + right;
        }
        return Math.max(left,right)+1;
    }
   }

8. 平衡二叉树：https://leetcode-cn.com/problems/balanced-binary-tree/

   class Solution {
    public boolean isBalanced(TreeNode root) {
        //类型：递归
        //思路：递归左右子树，判断能否同时到底。且左右子树深度不超过1
   
        if(root == null){
            return true;
        }
        return isBalanced(root.left) && isBalanced(root.right) && Math.abs(depth(root.left) - depth(root.right)) <= 1;
    }
   
    public int depth(TreeNode root){
        if(root == null){
            return 0;
        }
        return Math.max(depth(root.left),depth(root.right)) + 1;
    }
   }

9. 合并二叉树：https://leetcode-cn.com/problems/merge-two-binary-trees/

7. 重建二叉树

1. 前序和中序重建：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

   class Solution {
    //前序用数组存，中序用map存
    int[] pre;
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        pre = preorder;
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        //传入前序root为0，中序left为0，中序right为inorder.length-1;
        return recur(0,0,inorder.length-1);
    }
   
    public TreeNode recur(int pre_root,int in_left,int in_right){
        if(in_left > in_right){
            return null;
        }
        //提取root节点
        TreeNode root = new TreeNode(pre[pre_root]);
        int in_root = map.get(root.val);
   
        //根据前序的root节点重建，先左后右
        root.left = recur(pre_root+1,in_left,in_root-1);
        root.right = recur(pre_root+in_root-in_left+1,in_root+1,in_right);
   
        return root;
    }
   }

2. 中序和后序重建：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

   class Solution {
    //中序用map存
    Map<Integer,Integer> map = new HashMap<>();
    int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
   
        return recur(postorder,0,inorder.length-1);
    }
   
    public TreeNode recur(int[] postorder,int in_left,int in_right){
        if(in_left > in_right){
            return null;
        }
   
        TreeNode root = new TreeNode(postorder[postIndex--]);
        int in_root = map.get(root.val);
   
        //根据后序的root重建，先右后左
        root.right = recur(postorder,in_root+1,in_right);
        root.left = recur(postorder,in_left,in_root-1);
   
        return root;
    }
   }