框架

void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

1.二叉树的遍历（递归和非递归实现复习）

• 前序遍历
  先复习递归方法（模板）

public class Code144 {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

  //先复习递归实现
    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        process(root, list);
        return list;
    }

    public void process(TreeNode root, List<Integer> list){
        if(root == null)
            return;
        list.add(root.val);
        process(root.left, list);
        process(root.right, list);
    }

非递归方法：利用栈（压1弹2，先右后左）

//非递归实现
    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        //ctrl+H 继承自vector类 成员函数push pop peek
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            //出1压2
            list.add(cur.val);
            //先压右左才会先出左右
            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);
        }
        return list;
    }

• 中序遍历
  递归实现

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;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        //递归模板
        process(root, list);
        return list;
    }
    public void process(TreeNode root, List<Integer> list){
         if(root == null)
            return;
        process(root.left, list);
        list.add(root.val);
        process(root.right, list);
    }

非递归实现：看为是左数序列的集合

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        //看为是左树长序列的集合，stack保存
        Stack<TreeNode> stack = new Stack<>();
        process(root, stack);
        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();
            list.add(cur.val);
            //右树有节点酒压入右孩子的左序列
            if(cur.right != null){
                process(cur.right, stack);
            }
        }
        return list;
    }

    //左序列节点全部压入栈
    public void process(TreeNode root, Stack<TreeNode> stack){
        for(TreeNode p = root; p != null; p = p.left){
            stack.push(p);
        }
    }

图解.png

• 后序遍历
  前序非递归时候先压右再压左，最后list逆序即可

List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        //ctrl+H 继承自vector类 成员函数push pop peek
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            //出1压2
            list.add(cur.val);
            //先压左右才会先出右左
            if (cur.left != null)
                stack.push(cur.left);
            if (cur.right != null)
                stack.push(cur.right);

        }
        //此时list为前右左
        //逆序即为左右前
        Collections.reverse(list);
        return list;

• 层序遍历
  典型的先进先出结构，使用Deque api实现，出一个进两个，每次循环打印一层的节点

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        //典型的先进先出 用双端队列deque
        Deque<TreeNode> queue = new LinkedList<>();
        if(root == null)
            return list;
        queue.offer(root);

        while(!queue.isEmpty()){
            List<Integer> l = new ArrayList<>();
            int num = queue.size();//当前队中节点个数
            //出队一个进队两个，并记录加入的节点个数
            while (num > 0){
                TreeNode cur = queue.pollLast();
                l.add(cur.val);
                num--;
                if(cur.left != null)
                    queue.offerFirst(cur.left);
                if(cur.right != null)
                    queue.offerFirst(cur.right);
            }
            list.add(l);
        }
        return list;
    }

2 树的递归

• 快排复习

public static void quickSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        quickSort(nums, 0, nums.length - 1);
    }

    public static void quickSort(int[] nums, int l, int r) {
        if (l < r) {
            //加入了随机选取
            swap(nums, l + (int) (Math.random() * (r - l + 1)), r);
            int[] p = partition(nums, l, r);
            //针对小于区快排
            quickSort(nums, l, p[0] - 1);
            //针对大于区快排
            quickSort(nums, p[1] + 1, r);
        }
    }

    public static int[] partition(int[] nums, int l, int r) {
        int less = l - 1;
        int more = r;
        while (l < more) {
            //遇到小于就加入小于区
            if (nums[l] < nums[r]) {
                swap(nums, ++less, l++);
            } else if (nums[l] > nums[r]) {
                //遇到大于就加入大于区
                swap(nums, --more, l);
            } else {
                //等于保持不变
                l++;
            }
        }
        //把base数和大于区首个数交换，则现在是  小于区  等于区 大于区
        swap(nums, more, r);
        //返回等于区的首尾
        return new int[] { less + 1, more };
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

• 复习归并排序

public static void mergeSort(int[] nums){
        if(nums == null || nums.length <= 1)
            return;
        int[] temp = new int[nums.length];
        mergeSort(nums, 0, nums.length-1, temp);
    }
    public static void mergeSort(int[] nums, int left, int right, int[] temp)
    {
        if(left == right)
            return;
        int mid = left + ((right - left)>>1);
        mergeSort(nums, left, mid, temp);
        mergeSort(nums, mid+1,right, temp);
        merge(nums, left, mid, right, temp);

    }
    public static void merge(int[] nums, int left, int mid,int right, int[] temp)
    {
        int i = left;
        int j = mid + 1;
        for(int k = left; k <= right; k++)
        {
            //左区或右区 还有剩余
            if(i > mid && j <= right)
                temp[k] = nums[j++];
            else if(j > right && i <=mid)
                temp[k] = nums[i++];
            //左小于右就先放入左，并i指针++
            else if(nums[i] <= nums[j])
                temp[k] = nums[i++];
            else
                //同样，左大于右，放入右，j指针++
                temp[k] = nums[j++];
        }
        //把tmp整理好的部分放回nums中
        copyArray0(temp, left, right,nums);
    }

    public static void copyArray0(int[] nums,int left, int right,int[] temp)
    {
        for(int i = left; i <= right; i++)
            temp[i] = nums[i];

    }

可以看出规律，一个是先序得到三个区然后递归小于区和大于区，一个是后序排序左区和右区然后合并两个排好序的区

• 从git来学

git常用基础：
从暂存区还原到工作目录，git checkout XXX文件；
将历史区文件还原到暂存区，

image.png

• git pull有两种拉取模式，merge和rebase方式拉取，前者会有很多分支，后者一条直线

  
  
  image.png
  
  
  image.png

• 最近公共祖先

  
  
  image.png

思路：
void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}
所以，只要看到二叉树的问题，先把这个框架写出来准没问题：
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
}
现在我们思考如何添加一些细节，把框架改造成解法。
labuladong 告诉你，遇到任何递归型的问题，无非就是灵魂三问：
1、这个函数是干嘛的？
2、这个函数参数中的变量是什么的是什么？
3、得到函数的递归结果，你应该干什么？

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // base case
    if (root == null) return null;
    if (root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 情况 1
    if (left != null && right != null) {
        return root;
    }
    // 情况 2
    if (left == null && right == null) {
        return null;
    }
    // 情况 3
    return left == null ? right : left;
}

这就是一个巧妙的地方了，因为这里是二叉树的后序遍历啊！前序遍历可以理解为是从上往下，而后序遍历是从下往上，就好比从p和q出发往上走，第一次相交的节点就是这个root，你说这是不是最近公共祖先呢？

• 写树相关的算法，简单说就是，先搞清楚当前root节点该做什么，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情

• 翻转二叉树

  
  
  翻转二叉树.png
  
  

  先序遍历思路：自顶向下

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;
    }

后续遍历思路（自底向上）：

//思路应该是用后序遍历，先反转好左子树和右子树，在反转root的左右
    public TreeNode invertTree(TreeNode root) {
        //base case
        if(root == null)
            return root;
        //后续遍历，左右子树已经完成反转
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        //左右子树不为空且反转好了
        if(left != null && right != null){
            swap(root, root.left, root.right);
        }else if(left == null && right == null){
            //左右子树都为空，返回root
            return root;
        }else if(left != null && right == null){
            //其中一个子树为空，则左右交换
            swap(root, root.left, null);
        }else
            //其中一个子树为空，则左右交换
            swap(root, null, root.right);
        return root;
    }
    public void swap(TreeNode root, TreeNode left, TreeNode right){
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }

• 填充每个节点的下一个右侧节点指针

  
  
  image.png

二叉树的问题难点在于，如何把题目的要求细化成每个节点需要做的事情，但是如果只依赖一个节点的话，肯定是没办法连接「跨父节点」的两个相邻节点的。

那么，我们的做法就是增加函数参数，一个节点做不到，我们就给他安排两个节点，「将每一层二叉树节点连接起来」可以细化成「将每两个相邻节点都连接起来」：

public Node connect(Node root) {
        if (root == null) return null;
        connectTwoNode(root.left, root.right);
        return root;
    }

    // 定义：输入两个节点，将它俩连接起来，同样的先序遍历
    void connectTwoNode(Node node1, Node node2) {
        if (node1 == null || node2 == null) {
            return;
        }
        /**** 前序遍历位置 ****/
        // 将传入的两个节点连接
        node1.next = node2;

        // 连接相同父节点的两个子节点
        connectTwoNode(node1.left, node1.right);
        connectTwoNode(node2.left, node2.right);
        // 连接跨越父节点的两个子节点
        connectTwoNode(node1.right, node2.left);
    }

• 二叉树展开为链表

  
  
  image.png

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;
      }
  }
  //可以用后序遍历
    public void flatten(TreeNode root) {
        if(root == null)
            return;
        //先对左右子树扁平化
        flatten(root.left);
        flatten(root.right);

        //开始flatten操作
        if(root.left != null && root.right != null) {
            TreeNode tmp = root.right;
            //左树转到右树，并把左树置null
            root.right = root.left;
            root.left = null;
            TreeNode tmp2 = null;
            for(TreeNode p = root.right; p !=null; p=p.right){
                tmp2 = p;
            }
            //原右树加到现右树末尾
            tmp2.right = tmp;
        }else if(root.left == null && root.right != null){
            return;
        }else if(root.left != null && root.right == null){
            root.right = root.left;
            root.left = null;
        }else
            return;
        return;
    }

官方答案：

// 定义：将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
    // base case
    if (root == null) return;

    flatten(root.left);
    flatten(root.right);

    /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
    TreeNode left = root.left;
    TreeNode right = root.right;

    // 2、将左子树作为右子树
    root.left = null;
    root.right = left;

    // 3、将原先的右子树接到当前右子树的末端
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
}

其实就是如何根据左右递归函数的结果构建目前的root函数：需要考虑到所有情况

• 思路
  把题目的要求细化，搞清楚根节点应该做什么，然后剩下的事情抛给前/中/后序的遍历框架就行了

• 最大二叉树

  
  
  654.png

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums.length == 0)
            return null;
        //操作，肯定是找到当前范围内最大值
        TreeNode res = process(nums, 0, nums.length - 1);
        return res;
    }
    public TreeNode process(int[] nums, int l, int r){
        if(l > r)
            return null;
        //先找当前根节点，然后再process左子树和右子树
        int pos = -1;
        int max = Integer.MIN_VALUE;
        //得到根节点在数组中的位置
        for (int i = l; i <= r; i++) {
            if(nums[i] > max) {
                max = nums[i];
                pos = i;
            }
        }
        //先序思路，先构建根节点
        TreeNode root = new TreeNode(max);
        //构建左树和右树
        root.left = process(nums, l, pos - 1);
        root.right = process(nums, pos + 1, r);
        return root;
    }

• 前序和中序构造二叉树

  
  
  image.png

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode res = process(preorder, 0, preorder.length-1,
                inorder, 0, inorder.length-1);
        return res;
    }
    public TreeNode process(int[] preorder, int pl, int pr,
                        int[] inorder, int il, int ir){
        //base case
        if(pl > pr || il > ir)
            return null;
        //首先可以得到根节点，先序构建树
        TreeNode root = new TreeNode(preorder[pl]);
        int pos = -1;
        //找到对应中序遍历的位置
        for (int i = il; i <= ir; i++) {
            if(preorder[pl] == inorder[i]){
                pos = i;
                break;
            }
        }
        //这里注意计算相对长度
        int leftSize = pos - il;
        int rightSize = pr- pl - leftSize;
        root.left = process(preorder, pl+1, pl+leftSize,
                inorder, il, pos - 1);
        root.right = process(preorder, pl+leftSize+1, pr,
                inorder, pos+1, ir);

        return root;
    }

• 中序和后序构建二叉树

  
  
  image.png

同样利用已知两组信息得到root节点和左右序列范围，先序思路构建二叉树

public TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode res = process(inorder, 0, inorder.length-1,
                postorder, 0, postorder.length-1);
        return res;
    }
    public TreeNode process(int[] order, int ol, int or,
                        int[] postorder, int pl, int pr){
        //base case
        if(ol > or || pl > pr)
            return null;
        //先根据中序后续搞定root节点
        TreeNode root = new TreeNode(postorder[pr]);
        int pos = -1;
        for (int i = ol; i <= or; i++) {
            if (order[i] == postorder[pr]){
                pos = i;
                break;
            }
        }
        int leftSize = pos - ol;
        int rightSize = or - pos;
        root.left = process(order, ol, pos - 1,
                postorder, pl, pl+leftSize-1);
        root.right = process(order, pos+1, or,
                postorder, pl+leftSize, pr-1);
        return root;
    }