1.二叉树的递归遍历

  • 144. 二叉树的前序遍历 ```java public List preorderTraversal(TreeNode root) { List ans = new ArrayList<>(); process(root, ans); return ans; }

private void process(TreeNode root, List ans) { if (root == null) { return; } ans.add(root.val); process(root.left, ans); process(root.right, ans); }

  2. - [145. 二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)
  3. ```java
  4. public List<Integer> postorderTraversal(TreeNode root) {
  5.     List<Integer> ans = new ArrayList<>();
  6.     process(root, ans);
  7.     return ans;
  8. }
  10. private void process(TreeNode root, List<Integer> ans) {
  11.     if (root == null) {
  12.         return;
  13.     }
  15.     process(root.left, ans);
  16.     process(root.right, ans);
  17.     ans.add(root.val);
  18. }
  • 94. 二叉树的中序遍历 ```java public List inorderTraversal(TreeNode root) { ArrayList list = new ArrayList<>(); process(root, list); return list; }

private void process(TreeNode node, List list) { if (node == null) { return; } process(node.left, list); list.add(node.val); process(node.right, list); }

  1. <a name="Tq3nc"></a>
  2. # 2. 二叉树的迭代遍历
  3. <a name="u1Hgy"></a>
  4. ## 前序遍历(迭代)
  6.    - [144. 二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)
  8. 前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。<br />为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。<br />![](https://cdn.nlark.com/yuque/0/2022/gif/2817263/1642723756371-54319d14-3855-47fa-8054-eb33f6468816.gif#clientId=u79753a31-56f3-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=443&id=u8f01f310&margin=%5Bobject%20Object%5D&originHeight=472&originWidth=530&originalType=url&ratio=1&rotation=0&showTitle=false&status=done&style=none&taskId=ua7ad18d7-3b2b-43f1-b3b2-7ce68470b8a&title=&width=497)[【来源：代码随想录】]()<br />（**注意代码中空节点不入栈**）
  9. ```java
  10. // 前序遍历顺序：中-左-右，入栈顺序：中-右-左
  11. public List<Integer> preorderTraversal(TreeNode root) {
  12.         List<Integer> ans = new ArrayList<>();
  13.         if (root == null) {
  14.             return ans;
  15.         }
  16.         Stack<TreeNode> stack = new Stack<>();
  17.         stack.push(root);
  18.         while (!stack.isEmpty()) {
  19.             TreeNode node = stack.pop();
  20.             ans.add(node.val);
  21.             if (node.right != null) {
  22.                 stack.push(node.right);
  23.             }
  24.             if (node.left != null) {
  25.                 stack.push(node.left);
  26.             }
  27.         }
  28.         return ans;
  29. }

前序遍历迭代的代码为何能如此简洁？

其实我们有两个操作：

  1. 处理：将元素放进result数组中
  2. 访问：遍历节点

前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以才能写出简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

中序遍历(迭代)

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
二叉树专题 - 图1【来源：代码随想录】

  2. public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> ans = new ArrayList<>();
  4.         if (root == null) {
  5.             return ans;
  6.         }
  7.         Stack<TreeNode> stack = new Stack<>();
  8.         TreeNode cur = root;
  9.         while (cur != null || !stack.isEmpty()) {
  10.             if (cur != null) {
  11.                 stack.push(cur);
  12.                 cur = cur.left;
  13.             } else {
  14.                 cur = stack.pop();
  15.                 ans.add(cur.val);
  16.                 cur = cur.right;
  17.             }
  18.         }
  19.         return ans;
  20. }

后序遍历(迭代)

145. 二叉树的后序遍历
先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：
所以后序遍历只需要前序遍历的代码稍作修改就可以了

  1. // 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
  2. public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> ans = new ArrayList<>();
  4.         if (root == null) {
  5.             return ans;
  6.         }
  7.         Stack<TreeNode> stack = new Stack<>();
  8.         stack.push(root);
  9.         while (!stack.isEmpty()) {
  10.             TreeNode node = stack.pop();
  11.             ans.add(node.val);
  12.             if (node.left != null) {
  13.                 stack.push(node.left);
  14.             }
  15.             if (node.right != null) {
  16.                 stack.push(node.right);
  17.             }
  18.         }
  19.         //翻转
  20.         Collections.reverse(ans);
  21.         return ans;
  22. }

总结

可以看出前序和中序是完全两种代码风格，并不像递归写法那样代码稍做调整，就可以实现前后中序。 这是因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！ 那么问题又来了，难道 二叉树前后中序遍历的迭代法实现，就不能风格统一么（即前序遍历 改变代码顺序就可以实现中序 和 后序）？ 当然可以，这种写法，还不是很好理解

3. 二叉树的层序遍历

102. 二叉树的层序遍历

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
二叉树专题 - 图2 【来源：代码随想录】

  1. public List<List<Integer>> levelOrder(TreeNode root) {
  2.         List<List<Integer>> ans = new ArrayList<>();
  3.         if (root == null) {s
  4.             return ans;
  5.         }
  6.         Queue<TreeNode> queue = new LinkedList<>();
  7.         queue.offer(root);
  8.         while (!queue.isEmpty()) {
  9.             int size = queue.size();
  10.             List<Integer> list = new ArrayList<>();
  11.             // 这里一定要使用固定大小size，不要使用queue.size()，因为que.size是不断变化的
  12.             for (int i = 0; i < size; i++) {
  13.                 TreeNode node = queue.poll();
  14.                 list.add(node.val);
  15.                 if (node.left != null) {
  16.                     queue.offer(node.left);
  17.                 }
  18.                 if (node.right != null) {
  19.                     queue.offer(node.right);
  20.                 }
  21.             }
  22.             ans.add(list);
  23.         }
  24.         return ans;
  25. }

107. 二叉树的层序遍历Ⅱ

相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。

  1. public List<List<Integer>> levelOrderBottom(TreeNode root) {
  2.     List<List<Integer>> ans = new ArrayList<>();
  3.     if (root == null) {
  4.         return ans;
  5.     }
  6.     Queue<TreeNode> queue = new LinkedList<>();
  7.     queue.offer(root);
  8.     while (!queue.isEmpty()) {
  9.         int size = queue.size();
  10.         List<Integer> list = new ArrayList<>();
  11.         for (int i = 0; i < size; i++) {
  12.             TreeNode node = queue.poll();
  13.             list.add(node.val);
  14.             if (node.left != null) {
  15.                 queue.add(node.left);
  16.             }
  17.             if (node.right != null) {
  18.                 queue.add(node.right);
  19.             }
  20.         }
  21.         ans.add(list);
  22.     }
  23.     Collections.reverse(ans);
  24.     return ans;
  25. }

199. 二叉树的右视图

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

  1. public List<Integer> rightSideView(TreeNode root) {
  2.     List<Integer> ans = new ArrayList<>();
  3.     if (root == null) {
  4.         return ans;
  5.     }
  6.     Queue<TreeNode> queue = new LinkedList<>();
  7.     queue.offer(root);
  8.     while (!queue.isEmpty()) {
  9.         int size = queue.size();
  10.         for (int i = 0; i < size; i++) {
  11.             TreeNode node = queue.poll();
  12.             if (node.left != null) {
  13.                 queue.offer(node.left);
  14.             }
  15.             if (node.right != null) {
  16.                 queue.offer(node.right);
  17.             }
  19.             if (i == size - 1) {
  20.                 ans.add(node.val);
  21.             }
  22.         }
  23.     }
  24.     return ans;
  25. }

637. 二叉树的层平均值

本题就是层序遍历的时候把一层求个总和在取一个均值

  1. public List<Double> averageOfLevels(TreeNode root) {
  2.     List<Double> ans = new ArrayList<>();
  3.     if (root == null) {
  4.         return ans;
  5.     }
  6.     Queue<TreeNode> queue = new LinkedList<>();
  7.     queue.offer(root);
  8.     while (!queue.isEmpty()) {
  9.         int size = queue.size();
  10.         double sum = 0;
  11.         for (int i = 0; i < size; i++) {
  12.             TreeNode node = queue.poll();
  13.             sum += node.val;
  14.             if (node.left != null) {
  15.                 queue.offer(node.left);
  16.             }
  17.             if (node.right != null) {
  18.                 queue.offer(node.right);
  19.             }
  20.         }
  21.         sum /= size;
  22.         ans.add(sum);
  23.     }
  24.     return ans;
  25. }

429. N叉树的层序遍历

这道题依旧是模板题，只不过一个节点有多个孩子了

  1. public List<List<Integer>> levelOrder(Node root) {
  2.     List<List<Integer>> ans = new ArrayList<>();
  3.     if (root == null) {
  4.         return ans;
  5.     }
  6.     Queue<Node> queue = new LinkedList<>();
  7.     queue.offer(root);
  8.     while (!queue.isEmpty()) {
  9.         int size = queue.size();
  10.         List<Integer> list = new ArrayList<>();
  11.         for (int i = 0; i < size; i++) {
  12.             Node node = queue.poll();
  13.             list.add(node.val);
  14.             for (Node child : node.children) {
  15.                 queue.offer(child);
  16.             }
  17.             if (i == size - 1) {
  18.                 ans.add(list);
  19.             }
  20.         }
  21.     }
  22.     return ans;
  23. }
  25. class Node {
  26.     public int val;
  27.     public List<Node> children;
  29.     public Node() {}
  31.     public Node(int _val) {
  32.         val = _val;
  33.     }
  35.     public Node(int _val, List<Node> _children) {
  36.         val = _val;
  37.         children = _children;
  38.     }
  39. }

515. 在每个树行中找最大值

层序遍历，取每一层的最大值

  1. public List<Integer> largestValues(TreeNode root) {
  2.     List<Integer> ans = new ArrayList<>();
  3.     if (root == null) {
  4.         return ans;
  5.     }
  6.     Queue<TreeNode> queue = new LinkedList<>();
  7.     queue.offer(root);
  8.     while (!queue.isEmpty()) {
  9.         int size = queue.size();
  10.         int max = Integer.MIN_VALUE;
  11.         for (int i = 0; i < size; i++) {
  12.             TreeNode node = queue.poll();
  13.             max = Math.max(max, node.val);
  14.             if (node.left != null) {
  15.                 queue.offer(node.left);
  16.             }
  17.             if (node.right != null) {
  18.                 queue.offer(node.right);
  19.             }
  20.         }
  21.         ans.add(max);
  22.     }
  23.     return ans;
  24. }

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

  1.  public Node connect(Node root) {
  2.         if (root == null) {
  3.             return root;
  4.         }
  6.         Queue<Node> queue = new LinkedList<>();
  7.         queue.offer(root);
  8.         while (!queue.isEmpty()) {
  9.             int size = queue.size();
  10.             for (int i = 0; i < size; i++) {
  11.                 Node node = queue.poll();
  12.                 if (node.left != null) {
  13.                     queue.offer(node.left);
  14.                 }
  15.                 if (node.right != null) {
  16.                     queue.offer(node.right);
  17.                 }
  19.                 if (i == size - 1) {
  20.                     node.next = null;
  21.                 } else {
  22.                     node.next = queue.peek();
  23.                 }
  24.             }
  25.         }
  26.         return root;
  28.     }

104. 二叉树的最大深度

  • 法一：层序遍历

    1. public int maxDepth(TreeNode root) {
    2.       if (root == null) {
    3.           return 0;
    4.       }
    5.       int ans = 0;
    6.       Queue<TreeNode> queue = new LinkedList<>();
    7.       queue.offer(root);
    8.       while (!queue.isEmpty()) {
    9.           int size = queue.size();
    10.           for (int i = 0; i < size; i++) {
    11.               TreeNode node = queue.poll();
    12.               if (node.left != null) {
    13.                   queue.offer(node.left);
    14.               }
    15.               if (node.right != null) {
    16.                   queue.offer(node.right);
    17.               }
    18.               if (i == size - 1) {
    19.                   ans++;
    20.               }
    21.           }
    22.       }
    23.       return ans;
    24.   }

  • 法二：递归

    1. public int maxDepth(TreeNode root) {
    2.       if (root == null) {
    3.           return 0;
    4.       }
    5.       return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    6. }

    111.二叉树的最小深度

    1. public int minDepth(TreeNode root) {
    2.   int ans = 0;
    3.   if (root == null) {
    4.       return ans;
    5.   }
    6.   Queue<TreeNode> queue = new LinkedList<>();
    7.   queue.offer(root);
    8.   int level = 0;
    9.   while (!queue.isEmpty()) {
    10.       int size = queue.size();
    11.       level++;
    12.       for (int i = 0; i < size; i++) {
    13.           TreeNode node = queue.poll();
    14.           if (node.left != null) {
    15.               queue.offer(node.left);
    16.           }
    17.           if (node.right != null) {
    18.               queue.offer(node.right);
    19.           }
    20.           if (node.left == null && node.right == null) {
    21.               ans = level;
    22.               return ans;
    23.           }
    24.       }
    25.   }
    26.   return ans;
    27. }

    4. 翻转二叉树

  • 前序遍历(递归) ```java // 前序遍历（递归） public TreeNode invertTree(TreeNode root) { if (root == null) {

    1.   return root;

    } preOrder(root); return root; }

private void preOrder(TreeNode root) { if (root == null) { return; } TreeNode tmp = root.left; root.left = root.right; root.right = tmp; preOrder(root.left); preOrder(root.right); }

  2. - 前序遍历(迭代)
  3. ```java
  4.  public TreeNode invertTree(TreeNode root) {
  5.         if (root == null) {
  6.             return root;
  7.         }
  8.         Stack<TreeNode> stack = new Stack<>();
  9.         stack.push(root);
  10.         while (!stack.isEmpty() ) {
  11.             TreeNode node = stack.pop();
  12.             TreeNode tmp = node.left;
  13.             node.left = node.right;
  14.             node.right = tmp;
  15.             if (node.right != null) {
  16.                 stack.push(node.right);
  17.             }
  18.             if (node.left != null) {
  19.                 stack.push(node.left);
  20.             }
  21.         }
  22.         return root;
  23.  }
  • 层序遍历
    1. // 层序遍历
    2. public TreeNode invertTree(TreeNode root) {
    3.   if (root == null) {
    4.       return root;
    5.   }
    6.   Queue<TreeNode> queue = new LinkedList<>();
    7.   queue.offer(root);
    8.   while (!queue.isEmpty()) {
    9.       TreeNode node = queue.poll();
    10.       TreeNode tmp = node.left;
    11.       node.left = node.right;
    12.       node.right = tmp;
    13.       if (node.left != null) {
    14.           queue.offer(node.left);
    15.       }
    16.       if (node.right != null) {
    17.           queue.offer(node.right);
    18.       }
    19.   }
    20.   return root;
    21. }

    5. 对称二叉树

    递归法

    首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！
    对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
    那么如果比较呢？
    比较的是两个子树的里侧和外侧的元素是否相等。如图所示：
    image.png
    【来源：代码随想录】
    那么遍历的顺序应该是什么样的呢？
    本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
    正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
    但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。 ```java public boolean isSymmetric(TreeNode root) {
    1.   return compare(root.left, root.right);
    }

private boolean compare(TreeNode left, TreeNode right) { if (left == null && right != null) { return false; } else if (left != null && right == null) { return false; } else if (left == null && right == null) { return true; } else if (left.val != right.val) { // left right都不为空 return false; } else { //比较外侧 boolean outside = compare(left.left, right.right); //比较内测 boolean inside = compare(left.right, right.left); return outside && inside; } }

  2. <a name="DYj8s"></a>
  3. ## 迭代法
  4. 这道题目我们也可以使用迭代法，但要注意，这里的迭代法可不是前中后序的迭代写法，因为本题的本质是判断两个树是否是相互翻转的，其实已经不是所谓二叉树遍历的前中后序的关系了。<br />这里我们可以使用队列来比较两个树（根节点的左右子树）是否相互翻转，（**注意这不是层序遍历**）
  6. 使用队列<br />通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等，如动画所示：<br />![](https://cdn.nlark.com/yuque/0/2022/gif/2817263/1642809778524-f60a86b7-7bf3-4608-8905-e7eac909024b.gif#clientId=u4d9ca84e-d725-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=u3bd4b95f&margin=%5Bobject%20Object%5D&originHeight=422&originWidth=634&originalType=url&ratio=1&rotation=0&showTitle=false&status=done&style=none&taskId=u7ca4fe75-d0c8-4240-af08-db3d8775962&title=)<br />【from代码随想录】<br />如下的条件判断和递归的逻辑是一样的。
  7. ```java
  8. // 使用队列法
  9. public boolean isSymmetric2(TreeNode root) {
  10.         Queue<TreeNode> queue = new LinkedList<>();
  11.         queue.offer(root.left);
  12.         queue.offer(root.right);
  13.         while (!queue.isEmpty()) {
  14.             TreeNode left = queue.poll();
  15.             TreeNode right = queue.poll();
  16.             if (left == null && right == null) {
  17.                 continue;
  18.             } else if (left == null || right == null || left.val != right.val) {
  19.                 return false;
  20.             }
  21.             queue.offer(left.left);
  22.             queue.offer(right.right);
  23.             queue.offer(left.right);
  24.             queue.offer(right.left);
  25.         }
  26.         return true;
  27. }

类似题目

100.相同的树

  • 递归做法 ```java

public boolean isSameTree(TreeNode p, TreeNode q) { return compare(p, q); }

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

  2.    - 队列做法
  3. ```java
  4. public boolean isSameTree2(TreeNode p, TreeNode q) {
  5.     Queue<TreeNode> queue = new LinkedList<>();
  6.     queue.offer(p);
  7.     queue.offer(q);
  8.     while (!queue.isEmpty()) {
  9.         TreeNode node1 = queue.poll();
  10.         TreeNode node2 = queue.poll();
  11.         if (node1 == null && node2 == null) {
  12.             continue;
  13.         } else if (node1 == null || node2 == null || node1.val != node2.val) {
  14.             return false;
  15.         }
  16.         queue.offer(node1.left);
  17.         queue.offer(node2.left);
  18.         queue.offer(node1.right);
  19.         queue.offer(node2.right);
  20.     }
  21.     return true;
  22. }

572.另一棵树的子树

  1. public boolean isSubtree(TreeNode s, TreeNode t) {
  2.         // 迭代的中序遍历
  3.         Stack<TreeNode> stack = new Stack<>();
  4.         TreeNode cur = s;
  5.         while (cur != null || !stack.isEmpty()) {
  6.             if (cur != null) {
  7.                 stack.push(cur);
  8.                 cur = cur.left;
  9.             } else {
  10.                 cur = stack.pop();
  11.                 if (compare(cur, t)) {
  12.                     return true;
  13.                 }
  14.                 cur = cur.right;
  15.             }
  16.         }
  17.         return false;
  18.     }
  20.     private boolean compare(TreeNode node1, TreeNode node2) {
  21.         if (node1 == null && node2 == null) {
  22.             return true;
  23.         } else if (node1 == null || node2 == null || node1.val != node2.val){
  24.             return false;
  25.         }
  26.         return compare(node1.left, node2.left) && compare(node1.right, node2.right);
  27.     }

6. 二叉树的最大深度

  • 注意二叉树深度和高度的区别！

    递归法

    本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
    而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

  • 后序做法 ```java //后序求root的高度，就是整棵树的深度 public int maxDepth(TreeNode root) { return getHeight(root); }

private int getHeight(TreeNode node) { if (node == null) { return 0; } int leftHeight = getHeight(node.left); int rightHeight = getHeight(node.right); return Math.max(leftHeight, rightHeight) + 1; }

  2. - 本题当然也可以使用前序，代码如下：(**充分表现出求深度回溯的过程**)
  3. ```java
  4.  // 真正的求root的深度
  5. public int result = 0;
  7. public int maxDepth2(TreeNode root) {
  8.     if (root == null) {
  9.         return result;
  10.     }
  11.     getDepth(root, 1);
  12.     return result;
  13. }
  15. private void getDepth(TreeNode node, int depth) {
  16.     result = Math.max(result, depth);  // 中
  17.     if (node.left == null && node.right == null) {
  18.         return;
  19.     }
  20.     if (node.left != null) {  // 左
  21.         getDepth(node.left, depth + 1);
  22.     }
  23.     if (node.right != null) { // 右
  24.         getDepth(node.right, depth + 1);
  25.     }
  26.     return;
  27. }

可以看出使用了前序（中左右）的遍历顺序，这才是真正求深度的逻辑！

迭代法

  1.  // 法三：迭代：层序遍历
  2.     public int maxDepth3(TreeNode root) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  6.         Queue<TreeNode> queue = new LinkedList<>();
  7.         queue.offer(root);
  8.         int depth = 0;
  9.         while (!queue.isEmpty()) {
  10.             int size = queue.size();
  11.             for (int i = 0; i < size; i++) {
  12.                 TreeNode node = queue.poll();
  13.                 if (node.left != null) {
  14.                     queue.offer(node.left);
  15.                 }
  16.                 if (node.right != null) {
  17.                     queue.offer(node.right);
  18.                 }
  19.                 if (i == size - 1) {
  20.                     depth++;
  21.                 }
  22.             }
  23.         }
  24.         return depth;
  25.     }

559. N 叉树的最大深度

  • 递归法 ```java public int maxDepth(Node root) { if (root == null) {
    1.    return 0;
    } int depth = 0; for (int i = 0; i < root.children.size(); i++) {
    1.    depth = Math.max(depth, maxDepth(root.children.get(i)));
    } return depth + 1; }

class Node { public int val; public List children;

  1. public Node() {}
  3. public Node(int _val) {
  4.     val = _val;
  5. }
  7. public Node(int _val, List<Node> _children) {
  8.     val = _val;
  9.     children = _children;
  10. }

};

  2. - 迭代法：层序遍历
  3. ```java
  4. public int maxDepth(Node root) {
  5.         if (root == null) {
  6.             return 0;
  7.         }
  8.         Queue<Node> queue = new LinkedList<>();
  9.         queue.offer(root);
  10.         int depth = 0;
  11.         while (!queue.isEmpty()) {
  12.             int size = queue.size();
  13.             for (int i = 0; i < size; i++) {
  14.                 Node node = queue.poll();
  15.                 for (Node child : node.children) {
  16.                     queue.offer(child);
  17.                 }
  18.                 if (i == size - 1) {
  19.                     depth++;
  20.                 }
  21.             }
  22.         }
  23.         return depth;
  24. }

7. 二叉树的最小深度

和二叉树的最大深度一个套路？

递归法

直觉上好像和求最大深度差不多，其实还是差不少的。
遍历顺序上依然是后序遍历（因为要比较递归返回之后的结果），但在处理中间节点的逻辑上，最大深度很容易理解，最小深度可有一个误区，如图：
image.png
【来源：代码随想录】
这就重新审题了，题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。，注意是叶子节点。
什么是叶子节点，左右孩子都为空的节点才是叶子节点！

  1.  // 递归法
  2. public int minDepth(TreeNode root) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  6.         int leftDepth = minDepth(root.left);
  7.         int rightDepth = minDepth(root.right);
  8.         if (root.left == null) {
  9.             return rightDepth + 1;
  10.         }
  11.         if (root.right == null) {
  12.             return leftDepth + 1;
  13.         }
  14.         // 左右节点都不为空
  15.         return 1 + Math.min(leftDepth, rightDepth);
  16. }

迭代法

  • 层序遍历
    1. // 迭代：层序遍历
    2. public int minDepth2(TreeNode root) {
    3.       int ans = 0;
    4.       if (root == null) {
    5.           return ans;
    6.       }
    7.       Queue<TreeNode> queue = new LinkedList<>();
    8.       queue.offer(root);
    9.       int level = 0;
    10.       while (!queue.isEmpty()) {
    11.           int size = queue.size();
    12.           level++;
    13.           for (int i = 0; i < size; i++) {
    14.               TreeNode node = queue.poll();
    15.               if (node.left != null) {
    16.                   queue.offer(node.left);
    17.               }
    18.               if (node.right != null) {
    19.                   queue.offer(node.right);
    20.               }
    21.               if (node.left == null && node.right == null) {
    22.                   ans = level;
    23.                   return ans;
    24.               }
    25.           }
    26.       }
    27.       return ans;
    28. }

8. 完全二叉树的节点个数

  1.    // 法一： 递归
  2.     public static int countNodes(TreeNode head) {
  3.         if (head == null) {
  4.             return 0;
  5.         }
  6.         int leftNum = countNodes(head.left);
  7.         int rightNum = countNodes(head.right);
  8.         return 1 + leftNum + rightNum;
  9.     }
  1. // 法二： 层序遍历
  2.     public static int countNodes2(TreeNode head) {
  3.         if (head == null) {
  4.             return 0;
  5.         }
  6.         Queue<TreeNode> queue = new LinkedList<>();
  7.         queue.offer(head);
  8.         int counts = 0;
  9.         while (!queue.isEmpty()) {
  10.             TreeNode node = queue.poll();
  11.             counts++;
  12.             if (node.left != null) {
  13.                 queue.offer(node.left);
  14.             }
  15.             if (node.right != null) {
  16.                 queue.offer(node.right);
  17.             }
  18.         }
  19.         return counts;
  20.     }

9. 平衡二叉树

递归

此时大家应该明白了既然要求比较高度，必然是要后序遍历。
递归三步曲分析：

  1. 明确递归函数的参数和返回值

参数：当前传入节点。
返回值：以当前传入节点为根节点的树的高度。
那么如何标记左右子树是否差值大于1呢？
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。

  1. public boolean isBalanced(TreeNode root) {
  2.         return getHeight(root) == -1 ? false : true;
  3. }
  5. public int getHeight(TreeNode node) {
  6.         if (node == null) {
  7.             return 0;
  8.         }
  10.         int leftHeight = getHeight(node.left);
  11.         if (leftHeight == -1) return -1;
  12.         int rightHeight = getHeight(node.right);
  13.         if (rightHeight == -1) return -1;
  14.         if (Math.abs(leftHeight - rightHeight) > 1) {
  15.             return -1;
  16.         }
  17.         return 1 + Math.max(leftHeight, rightHeight);
  18. }

10. 二叉树的所有路径

递归 + 回溯

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一一个路径在进入另一个路径。
前序遍历以及回溯的过程如图：
image.png
【来源代码随想录】

  1. public List<String> ans = new ArrayList<>();
  3. public List<String> binaryTreePaths(TreeNode root) {
  4.     List<Integer> paths = new ArrayList<>();
  5.     process(root, paths);
  6.     return ans;
  7. }
  9. //前序遍历 + 回溯
  10. private void process(TreeNode node, List<Integer> paths) {
  12.     paths.add(node.val); // 中
  14.     if (node.left == null && node.right == null) {  // 叶子节点
  15.         StringBuilder sb = new StringBuilder();
  16.         for (int i = 0; i < paths.size() - 1; i++) {
  17.             sb.append(paths.get(i)).append("->");
  18.         }
  19.         sb.append(paths.get(paths.size() - 1));
  20.         ans.add(sb.toString());
  21.         return;
  22.     }
  24.     if (node.left != null) {
  25.         process(node.left, paths);
  26.         paths.remove(paths.size() - 1);// 回溯
  27.     }
  29.     if (node.right != null) {
  30.         process(node.right, paths);
  31.         paths.remove(paths.size() - 1);// 回溯
  32.     }
  33. }

迭代

至于非递归的方式，我们可以依然可以使用前序遍历的迭代方式来模拟遍历路径的过程

  1. //法二： 迭代
  2. public List<String> binaryTreePaths2(TreeNode root) {
  3.     List<String> result = new ArrayList<>();
  4.     if (root == null) {
  5.         return result;
  6.     }
  7.     Stack<Object> stack = new Stack<>();
  8.     // 节点和路径同时入栈
  9.     stack.push(root);
  10.     stack.push(root.val + "");
  11.     while (!stack.isEmpty()) {
  12.         // 节点和路径同时出栈
  13.         String path = (String) stack.pop();
  14.         TreeNode node = (TreeNode) stack.pop();
  15.         // 若找到叶子节点
  16.         if (node.left == null && node.right == null) {
  17.             result.add(path);
  18.         }
  19.         //右子节点不为空
  20.         if (node.right != null) {
  21.             stack.push(node.right);
  22.             stack.push(path + "->" + node.right.val);
  23.         }
  24.         //左子节点不为空
  25.         if (node.left != null) {
  26.             stack.push(node.left);
  27.             stack.push(path + "->" + node.left.val);
  28.         }
  29.     }
  30.     return result;
  31. }

11.左叶子节点之和

递归法（后序）

  1.    public int sumOfLeftLeaves(TreeNode root) {
  2.         if (root.left == null && root.right == null) {
  3.             return 0;
  4.         }
  5.         return process(root,  null);
  6.     }
  8.     private int process(TreeNode node, TreeNode parent) {
  9.         if (node.left == null && node.right == null) {
  10.             if (node == parent.left) {
  11.                 return node.val;
  12.             } else {
  13.                 return 0;
  14.             }
  15.         }
  16.         int leftSum = 0;
  17.         if (node.left != null) {
  18.           leftSum = process(node.left, node);
  19.         }
  20.         int rightSum = 0;
  21.         if (node.right != null) {
  22.             rightSum = process(node.right, node);
  23.         }
  24.         return leftSum + rightSum;
  25.     }

迭代

  • 本题迭代法使用前中后序都是可以的，只要把左叶子节点统计出来，就可以了

    1. //迭代法：前序遍历
    2. public int sumOfLeftLeaves2(TreeNode root) {
    3.   int sum = 0;
    4.   if (root.left == null && root.right == null) {
    5.       return sum;
    6.   }
    7.   Stack<TreeNode> stack = new Stack<>();
    8.   stack.push(root);
    9.   while (!stack.isEmpty()) {
    10.       TreeNode node = stack.pop();
    11.       if (node.left != null && node.left.left == null && node.left.right == null) {
    12.           sum += node.left.val;
    13.       }
    14.       if (node.right != null) {
    15.           stack.push(node.right);
    16.       }
    17.       if (node.left != null) {
    18.           stack.push(node.left);
    19.       }
    20.   }
    21.   return sum;
    22. }

    12. 找树左下角的值

    1. public static int findBottomLeftValue(TreeNode root) {
    2.   if (root == null) {
    3.       return 0;
    4.   }
    5.   Queue<TreeNode> queue = new LinkedList<>();
    6.   queue.offer(root);
    7.   while (!queue.isEmpty()) {
    8.       int size = queue.size();
    9.       TreeNode head = null;
    10.       for (int i = 0; i < size; i++) {
    11.           TreeNode node = queue.poll();
    12.           if (i == 0) {
    13.               head = node;
    14.           }
    16.           if (node.left != null) {
    17.               queue.offer(node.left);
    18.           }
    19.           if (node.right != null) {
    20.               queue.offer(node.right);
    21.           }
    23.           if (i == (size - 1) && queue.isEmpty()) {
    24.               return head.val;
    25.           }
    26.       }
    27.   }
    28.   return 0;
    29. }

13. 路径总和

  • 112. 路径总和

    • 递归法

      1. public boolean hasPathSum(TreeNode root, int targetSum) {
      2.    if (root == null) {
      3.        return false;
      4.    }
      5.    targetSum -= root.val;
      6.    // 叶子节点
      7.    if (root.left == null && root.right == null) {
      8.        return targetSum == 0;
      9.    }
      11.    if (root.left != null) {
      12.        boolean left = hasPathSum(root.left, targetSum);
      13.        if (left) {
      14.            return true;
      15.        }
      16.    }
      18.    if (root.right != null) {
      19.        boolean right = hasPathSum(root.right, targetSum);
      20.        if (right) {
      21.            return true;
      22.        }
      23.    }
      24.    return false;
      25. }

  • 迭代法

    1. // 法二：迭代
    2.   public boolean hasPathSum2(TreeNode root, int targetSum) {
    3.       if (root == null) return false;
    4.       Stack<Object> stack = new Stack<>();
    5.       stack.push(root);
    6.       stack.push(root.val);
    7.       while (!stack.isEmpty()) {
    8.           int sum = (int) stack.pop();
    9.           TreeNode node = (TreeNode) stack.pop();
    10.           if (node.left == null && node.right == null && sum == targetSum) {
    11.               return true;
    12.           }
    14.           if (node.right != null) {
    15.               stack.push(node.right);
    16.               stack.push(sum + node.right.val);
    17.           }
    18.           if (node.left != null) {
    19.               stack.push(node.left);
    20.               stack.push(sum + node.left.val);
    21.           }
    22.       }
    23.       return false;
    24.   }

14. 路径总和Ⅱ

  1. private List<List<Integer>> res = new ArrayList<>();
  4. public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
  5.     if (root == null) {
  6.         return res;
  7.     }
  8.     List<Integer> path = new ArrayList<>();
  9.     path.add(root.val);
  10.     process(root, targetSum - root.val, path);
  11.     return res;
  12. }
  14. private void process(TreeNode node, int targetSum, List<Integer> path) {
  16.     if (node.left == null && node.right == null && targetSum == 0) {
  17.         List<Integer> list = new ArrayList<>();
  18.         for (int i : path) {
  19.             list.add(i);
  20.         }
  21.         res.add(list);
  22.         return;
  23.     }
  25.     if (node.left != null) {
  26.         path.add(node.left.val);
  27.         targetSum -= node.left.val;
  28.         process(node.left, targetSum, path);
  29.         path.remove(path.size() - 1);  //回溯
  30.         targetSum += node.left.val;  //回溯
  31.     }
  33.     if (node.right != null) {
  34.         path.add(node.right.val);
  35.         targetSum -= node.right.val;
  36.         process(node.right, targetSum, path);
  37.         path.remove(path.size() - 1);  //回溯
  38.         targetSum += node.right.val;  //回溯
  39.     }
  40. }

15.根据遍历结果构造二叉树

106.⭐从中序与后序遍历序列构造二叉树

截图_20222924092959.png

  1.   public TreeNode buildTree(int[] inorder, int[] postorder) {
  2.         return process(inorder, 0, inorder.length, postorder, 0, postorder.length);
  3.     }
  5.     // 区间不变量：左闭右开
  6.     private TreeNode process(int[] inorder, int L1, int R1, int[] postorder, int L2, int R2) {
  7.         // 一个元素都没有
  8.         if (R1 - L1 < 1) {
  9.             return null;
  10.         }
  11.         // 只有一个元素了
  12.         if (R1 - L1 == 1) {
  13.             return new TreeNode(inorder[L1]);
  14.         }
  15.         // 后序数组postorder里最后一个即为根结点
  16.         int rootVal = postorder[R2 - 1];
  17.         TreeNode root = new TreeNode(rootVal);
  18.         int rootIndex = 0;
  19.         // 根据根结点的值找到该值在中序数组inorder里的位置
  20.         for ( rootIndex = L1; rootIndex < R1; rootIndex++) {
  21.             if (inorder[rootIndex] == rootVal) {
  22.                 break;
  23.             }
  24.         }
  26.         // 根据rootIndex划分左右子树
  27.         root.left = process(inorder, L1, rootIndex, postorder, L2, L2 + (rootIndex - L1));
  28.         root.right = process(inorder, rootIndex + 1, R1, postorder, L2 + (rootIndex - L1), R2 - 1);
  29.         return root;
  30.     }

105.⭐从前序与中序遍历序列构造二叉树

截图_20224924094919.png

  1.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  2.         return process(preorder, 0, preorder.length, inorder, 0, inorder.length);
  3.     }
  5.     //不变量原则：左闭右开
  6.     private TreeNode process(int[] preorder, int L1, int R1, int[] inorder, int L2, int R2) {
  7.         if (R1 - L1 < 1) {
  8.             return null;
  9.         }
  11.         if (R1 - L1 == 1) {
  12.             return new TreeNode(preorder[L1]);
  13.         }
  15.         int rootVal = preorder[L1];
  16.         TreeNode root = new TreeNode(rootVal);
  17.         int rootIndex = 0;
  18.         for (rootIndex = L2; rootIndex < R2; rootIndex++) {
  19.             if (inorder[rootIndex] == rootVal) {
  20.                 break;
  21.             }
  22.         }
  24.         root.left = process(preorder, L1 + 1, L1 + 1 + (rootIndex - L2), inorder, L2, rootIndex);
  25.         root.right = process(preorder, L1 + 1+ (rootIndex - L2), R1, inorder, rootIndex + 1, R2);
  26.         return root;
  27.     }

思考题

前序和中序可以唯一确定一棵二叉树。
后序和中序可以唯一确定一棵二叉树。
那么前序和后序可不可以唯一确定一棵二叉树呢？
前序和后序不能唯一确定一棵二叉树！，因为没有中序遍历无法确定左右部分，也就是无法分割。

16. 最大二叉树

  1.  public TreeNode constructMaximumBinaryTree(int[] nums) {
  2.      return process(nums, 0, nums.length);
  3.  }
  5. // 不变量原则： 左闭右开
  6. private TreeNode process(int[] nums, int L, int R) {
  7.     if (R - L< 1) {
  8.         return null;
  9.     }
  11.     if (R - L == 1) {
  12.         return new TreeNode(nums[L]);
  13.     }
  15.     int max = Integer.MIN_VALUE;
  16.     int maxIndex = 0;
  17.     for (int i = L; i < R; i++) {
  18.         if (nums[i] > max) {
  19.             max = nums[i];
  20.             maxIndex = i;
  21.         }
  22.     }
  23.     TreeNode root = new TreeNode(max);
  24.     root.left = process(nums, L, maxIndex);
  25.     root.right = process(nums, maxIndex + 1, R);
  26.     return root;
  27. }

17.合并二叉树

  • 递归

    1. public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    2.   if (root1 == null) {// 如果root1为空，合并之后就应该是root2
    3.       return root2;
    4.   }
    5.   if (root2 == null) {// 如果root2为空，合并之后就应该是root1
    6.       return root1;
    7.   }
    9.   TreeNode root = new TreeNode(root1.val + root2.val);
    10.   root.left = mergeTrees(root1.left, root2.left);
    11.   root.right = mergeTrees(root1.right, root2.right);
    12.   return root;
    13. }

  • 使用队列

    1. // 使用队列迭代
    2.   public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    3.       if (root1 == null) return root2;
    4.       if (root2 ==null) return root1;
    5.       Queue<TreeNode> queue = new LinkedList<>();
    6.       queue.offer(root1);
    7.       queue.offer(root2);
    8.       while (!queue.isEmpty()) {
    9.           TreeNode node1 = queue.poll();
    10.           TreeNode node2 = queue.poll();
    11.           // 此时两个节点一定不为空，val相加
    12.           node1.val = node1.val + node2.val;
    13.           // 如果两棵树左节点都不为空，加入队列
    14.           if (node1.left != null && node2.left != null) {
    15.               queue.offer(node1.left);
    16.               queue.offer(node2.left);
    17.           }
    18.           // 如果两棵树右节点都不为空，加入队列
    19.           if (node1.right != null && node2.right != null) {
    20.               queue.offer(node1.right);
    21.               queue.offer(node2.right);
    22.           }
    23.           // 若node1的左节点为空，直接赋值
    24.           if (node1.left == null && node2.left != null) {
    25.               node1.left = node2.left;
    26.           }
    27.           // 若node2的右节点为空，直接赋值
    28.           if (node1.right == null && node2.right != null) {
    29.               node1.right = node2.right;
    30.           }
    31.       }
    32.       return root1;
    33.   }

18.二叉搜索树中的搜索

  • 法一：递归

    1. public TreeNode searchBST(TreeNode root, int val) {
    2.       if (root == null) {
    3.           return root;
    4.       }
    5.       if (root.val == val) {
    6.           return root;
    7.       }
    9.       if (root.val < val) {
    10.           return searchBST(root.right, val);
    11.       } else if (root.val > val) {
    12.           return searchBST(root.left, val);
    13.       }
    14.       return null;
    15.   }

  • 法二：非递归

一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。
对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。
对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。
而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。
例如要搜索元素为3的节点，我们不需要搜索其他节点，也不需要做回溯，查找的路径已经规划好了。

  1.  //法二：迭代
  2.     public TreeNode searchBST2(TreeNode root, int val) {
  3.         while (root != null) {
  4.             if (root.val > val) {
  5.                 root = root.left;
  6.             } else if (root.val < val) {
  7.                 root = root.right;
  8.             } else {
  9.                 return root;
  10.             }
  11.         }
  12.         return null;
  13.     }

19.验证二叉搜索树

  • 思路：中序遍历下，输出的二叉搜索树节点的数值是有序序列。有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了


递归法

  • 可以递归中序遍历将二叉搜索树转变成一个数组，然后只要比较一下，这个数组是否是有序的，注意二叉搜索树中不能有重复元素， 把二叉树转变为数组来判断，是最直观的，但其实不用转变成数组，可以在递归遍历的过程中直接判断是否有序。

  • 这道题目比较容易陷入两个陷阱：

  • 陷阱1：不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。

    • 我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点

      • 截图_20223125083112.png
      • 节点10大于左节点5，小于右节点15，但右子树里出现了一个6 这就不符合了！ ```java //前一个节点 private TreeNode pre = null;

      public boolean isValidBST(TreeNode root){ if (root == null) {

      1.    return true;

      }

      boolean left = isValidBST(root.left); // 左

      //注意重复值 if (pre!=null && pre.val >= root.val) return false;

      pre = root; // 记录前一个节点

      boolean right = isValidBST(root.right); // 右 return left && right; }

  2. <a name="JTA2a"></a>
  3. ## 迭代法
  5. - 对中序遍历的迭代法稍加改动即可
  6. ```java
  7.  //法二：迭代
  8.     public boolean isValidBST2(TreeNode root){
  9.         if (root == null) {
  10.             return true;
  11.         }
  13.         Stack<TreeNode> stack = new Stack<>();
  14.         TreeNode cur = root;
  15.         TreeNode pre = null;
  16.         while (cur != null || !stack.isEmpty()) {
  17.             if (cur != null) {
  18.                 stack.push(cur);
  19.                 cur = cur.left;
  20.             } else {
  21.                 cur = stack.pop();
  22.                 if (pre != null && pre.val >= cur.val) return false;
  23.                 pre = cur;
  24.                 cur = cur.right;
  25.             }
  26.         }
  27.         return true;
  28.     }

20.二叉搜索树的最小绝对差

  • 利用中序遍历是升序的特性，记录上一个遍历的节点

  • 递归法

    1. private TreeNode pre = null; // 记录上一个遍历的节点
    2.   private int min = Integer.MAX_VALUE;
    4.   public int getMinimumDifference(TreeNode root) {
    5.       process(root);
    6.       return min;
    7.   }
    9.   private void process(TreeNode root) {
    10.       if (root == null) return;
    12.       process(root.left);
    13.       if (pre != null) {
    14.           min = Math.min(min, root.val - pre.val);
    15.       }
    16.       pre = root;
    17.       process(root.right);
    18.   }

  • 改迭代法

    1.   // 法二:迭代
    2.   public int getMinimumDifference2(TreeNode root) {
    4.       Stack<TreeNode> stack = new Stack<>();
    5.       TreeNode cur = root;
    6.       TreeNode pre = null; // 记录上一个遍历的节点
    7.       int min = Integer.MAX_VALUE;
    8.       while (cur != null || !stack.isEmpty()) {
    9.           if (cur != null) {
    10.               stack.push(cur);
    11.               cur = cur.left;
    12.           } else {
    13.               cur = stack.pop();
    14.               if (pre != null) {
    15.                   min = Math.min(min, cur.val - pre.val);
    16.               }
    17.               pre = cur;
    18.               cur = cur.right;
    19.           }
    20.       }
    21.       return min;
    22.   }

21.二叉搜索树中的众数

  • 如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，取前面高频的元素的集合。

至于用前中后序那种遍历也不重要，因为就是要全遍历一遍，怎么个遍历法都行，层序遍历都没毛病！
这里采用前序遍历

  1.     private HashMap<Integer, Integer> map = new HashMap<>();
  2.     public int[] findMode(TreeNode root) {
  3.         if (root == null) {
  4.             return new int[0];
  5.         }
  6.         process(root);
  7.         List<Integer> list = new ArrayList<>();
  9.         int maxCount = Integer.MIN_VALUE;
  10.         for (Integer value : map.values()) {
  11.             maxCount = Math.max(maxCount, value);
  12.         }
  14.         for (Integer key : map.keySet()) {
  15.             Integer i = map.get(key);
  16.             if ( i == maxCount) {
  17.                 list.add(key);
  18.             }
  19.         }
  21.         int[] ans = new int[list.size()];
  22.         int index = 0;
  23.         for (int o : list) {
  24.             ans[index++] = o;
  25.         }
  26.         return ans;
  27.     }
  29.     private void process(TreeNode node) {
  30.         if (node == null) {
  31.             return;
  32.         }
  34.         process(node.left);
  35.         map.put(node.val, map.getOrDefault(node.val, 0) + 1);
  36.         process(node.right);
  37.     }

  • 法二:利用二叉搜索树中序遍历的特性,

    1.    ArrayList<Integer> resList;
    2.   int maxCount;
    3.   int count;
    4.   TreeNode pre;
    6.   public int[] findMode(TreeNode root) {
    7.       resList = new ArrayList<>();
    8.       maxCount = 0;
    9.       count = 0;
    10.       pre = null;
    11.       findMode1(root);
    12.       int[] res = new int[resList.size()];
    13.       for (int i = 0; i < resList.size(); i++) {
    14.           res[i] = resList.get(i);
    15.       }
    16.       return res;
    17.   }
    19.   public void findMode1(TreeNode root) {
    20.       if (root == null) {
    21.           return;
    22.       }
    23.       findMode1(root.left);
    25.       int rootValue = root.val;
    26.       // 计数
    27.       if (pre == null || rootValue != pre.val) {
    28.           count = 1;
    29.       } else {
    30.           count++;
    31.       }
    32.       // 更新结果以及maxCount
    33.       if (count > maxCount) {
    34.           resList.clear();
    35.           resList.add(rootValue);
    36.           maxCount = count;
    37.       } else if (count == maxCount) {
    38.           resList.add(rootValue);
    39.       }
    40.       pre = root;
    42.       findMode1(root.right);
    43.   }

22.二叉树的最近公共祖先⭐

  • 二叉树的递归套路

https://www.yuque.com/xcc/cqqo4i/ssqeng

  1.    public class Info {
  2.         // 最近交汇的点
  3.         public TreeNode ans;
  4.         public boolean findO1;
  5.         public boolean findO2;
  7.         public Info(TreeNode ans, boolean findO1, boolean findO2) {
  8.             this.ans = ans;
  9.             this.findO1 = findO1;
  10.             this.findO2 = findO2;
  11.         }
  12.     }
  14.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode o1, TreeNode o2) {
  15.         return process(root, o1, o2).ans;
  17.     }
  19.     private Info process(TreeNode node, TreeNode o1, TreeNode o2) {
  20.         if (node == null) {
  21.             return new Info(null, false, false);
  22.         }
  24.         Info leftInfo = process(node.left, o1, o2);
  25.         Info rightInfo = process(node.right, o1, o2);
  27.         boolean findO1 = node == o1 || leftInfo.findO1 || rightInfo.findO1;
  28.         boolean findO2 = node == o2 || leftInfo.findO2 || rightInfo.findO2;
  29.         TreeNode ans = null;
  30.         if (leftInfo.ans != null) {
  31.             ans = leftInfo.ans;
  32.         }
  33.         if (rightInfo.ans != null) {
  34.             ans = rightInfo.ans;
  35.         }
  36.         if (ans == null) {
  37.             if (findO1 && findO2) {
  38.                 ans = node;
  39.             }
  40.         }
  41.         return new Info(ans, findO1, findO2);
  42.     }

23.二叉搜索树的最近公共祖先

  • 这道题没有普通二叉树那题的做法麻烦，因为可以利用二叉搜索树的有序的特性 ```java public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

    1.   if (root == null) {
    2.       return null;
    3.   }
    5.   if (root.val > p.val && root.val > q.val) {
    6.       return lowestCommonAncestor(root.left, p, q);
    7.   }
    9.   if (root.val < p.val && root.val < q.val) {
    10.       return lowestCommonAncestor(root.right, p, q);
    11.   }
    13.   return root;

    }

  4. <a name="M8DFM"></a>
  5. # [701.二叉搜索树中的插入操作](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
  6. ```java
  7.  public TreeNode insertIntoBST(TreeNode root, int val) {
  8.         TreeNode insert = new TreeNode(val);
  9.         if (root == null) {
  10.             return insert;
  11.         }
  13.         TreeNode cur = root;
  14.         while (cur != null) {
  15.             if (val < cur.val && cur.left != null) {
  16.                 cur = cur.left;
  17.             }
  18.             if (val < cur.val && cur.left == null) {
  19.                 cur.left = insert;
  20.                 break;
  21.             }
  22.             if (val > cur.val && cur.right != null) {
  23.                 cur = cur.right;
  24.             }
  25.             if (val > cur.val && cur.right == null) {
  26.                 cur.right = insert;
  27.                 break;
  28.             }
  29.         }
  30.         return root;
  31.     }

450.删除二叉搜索树中的节点⭐

  • 第一种情况：没找到删除的节点
  • 找到删除的节点
    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
    • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
    • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

第五种情况有点难以理解，看下面动画：
二叉树专题 - 图9
动画中棵二叉搜索树中，删除元素7， 那么删除节点（元素7）的左孩子就是5，删除节点（元素7）的右子树的最左面节点是元素8。
将删除节点（元素7）的左孩子放到删除节点（元素7）的右子树的最左面节点（元素8）的左孩子上，就是把5为根节点的子树移到了8的左孩子的位置。

  • 迭代写法 ```java public TreeNode deleteNode(TreeNode root, int key) {

    1.   if (root == null) {
    2.       return root;
    3.   }
    4.   TreeNode pre = null;
    5.   TreeNode cur = root;
    7.   while (cur != null) {
    8.       if (key == cur.val) {
    9.           break;
    10.       }
    11.       pre = cur;
    12.       if (key < cur.val) {
    13.           cur = cur.left;
    14.       }else {
    15.           cur = cur.right;
    16.       }
    17.   }
    19.   //要删除的就是根节点
    20.   if (pre == null) {
    21.       return deleteOneNode(cur);
    22.   }
  1.     if (pre.left != null && pre.left.val == key) {
  2.         pre.left = deleteOneNode(cur);
  3.     }
  4.     if (pre.right != null && pre.right.val == key) {
  5.         pre.right = deleteOneNode(cur);
  6.     }
  7.     return root;
  8. }
  10. // 删除节点逻辑, 返回新的根节点
  11. private TreeNode deleteOneNode(TreeNode cur) {
  12.     if (cur.right == null) { //删除叶子节点 或 左子不为空，右子为空的节点
  13.        return cur.left;
  14.     } else if (cur.left == null){  // 删除左子为空，右子不为空的节点
  15.         return cur.right;
  16.     }
  18.     //删除度为2的节点
  19.     TreeNode node = cur.right;
  20.     while (node.left != null) {
  21.         node = node.left;
  22.     }
  23.     node.left = cur.left;
  24.     return cur.right;
  25. }
  2. - 递归写法
  3. ```java
  5.     //递归写法， 返回删除后整树的新头节点
  6.     public TreeNode deleteNode2(TreeNode root, int key) {
  7.         if (root == null) {
  8.             return root;
  9.         }
  10.         if (root.val == key) {
  11.             // 叶子节点
  12.             if (root.left == null && root.right == null) {
  13.                 root = null;
  14.                 return root;
  15.             } else if (root.left == null) { //度为1的节点
  16.                 root = root.right;
  17.                 return root;
  18.             } else if (root.right == null) { //度为1的节点
  19.                 root = root.left;
  20.                 return root;
  21.             } else {//度为2的节点
  22.                 TreeNode node = root.right;
  23.                 while (node.left != null) {
  24.                     node = node.left;
  25.                 }
  26.                 node.left = root.left;
  27.                 root = root.right;
  28.                 return root;
  29.             }
  30.         }
  31.         if (key < root.val) {
  32.             root.left = deleteNode2(root.left, key);
  33.         }
  34.         if (key > root.val) {
  35.             root.right = deleteNode(root.right, key);
  36.         }
  37.         return root;
  38.     }

669.修剪二叉搜索树⭐

递归法

来源【代码随想录】
[1, 3]区间在二叉搜索树的中可不是单纯的节点3和左孩子节点0就决定的，还要考虑节点0的右子树。
我们在重新关注一下第二个示例，如图：
image.png
所以以上的代码是不可行的！
从图中可以看出需要重构二叉树，想想是不是本题就有点复杂了。
其实不用重构那么复杂。
在上图中我们发现节点0并不符合区间要求，那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了（就是把节点0从二叉树中移除），如图：
image.png

  1. //法一：递归
  2. //传入一个根节点，返回修剪后的新的整树根节点
  3. public TreeNode trimBST(TreeNode root, int low, int high) {
  4.     if (root == null) {
  5.         return root;
  6.     }
  7.     if (root.val < low) {
  8.         return trimBST(root.right, low, high);
  10.     }
  11.     if (root.val > high) {
  12.         return trimBST(root.left, low, high);
  13.     }
  14.     root.left = trimBST(root.left, low, high);
  15.     root.right = trimBST(root.right, low, high);
  17.     return root;
  18. }

迭代法

因为二叉搜索树的有序性，不需要使用栈模拟递归的过程。
在剪枝的时候，可以分为三步：

  • 将root移动到[L, R] 范围内，注意是左闭右闭区间
  • 剪枝左子树

  • 剪枝右子树

    1.   //法二：迭代
    2.   public TreeNode trimBST2(TreeNode root, int low, int high) {
    3.       if (root == null) return null;
    5.       //处理头节点, 让root移动到[L, R]范围内
    6.       while (root != null && (root.val < low || root.val > high)) {
    7.           if (root.val < low) {
    8.               root = root.right;
    9.           } else {
    10.               root = root.left;
    11.           }
    12.       }
    14.       TreeNode cur = root;
    15.       // 此时root已经在[L, R] 范围内，处理左孩子元素小于low的情况
    16.       while (cur != null) {
    17.           while (cur.left != null && cur.left.val < low) {
    18.               cur.left = cur.left.right;
    19.           }
    20.           cur = cur.left;
    21.       }
    23.       cur = root;
    25.       // 此时root已经在[L, R] 范围内，处理右孩子大于high的情况
    26.       while (cur != null) {
    27.           while (cur.right != null && cur.right.val > high) {
    28.               cur.right = cur.right.left;
    29.           }
    30.           cur = cur.right;
    31.       }
    32.       return root;
    33.   }

108.将有序数组转换为二叉搜索树

本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
分割点就是数组中间位置的节点。
那么为问题来了，如果数组长度为偶数，中间节点有两个，取哪一个？
取哪一个都可以，只不过构成了不同的平衡二叉搜索树。

首先取数组中间元素的位置，不难写出int mid = (left + right) / 2;，这么写其实有一个问题，就是数值越界，例如left和right都是最大int，这么操作就越界了，在二分法中尤其需要注意！

  1.  public TreeNode sortedArrayToBST(int[] nums) {
  2.         return process(nums, 0, nums.length - 1);
  3.  }
  5. //左闭右开
  6. private TreeNode process(int[] nums, int L, int R) {
  7.     if (L > R) {
  8.         return null;
  9.     }
  10.     //  int mid = (L + R) >> 1; // 这样写存在越界问题
  11.     int mid = L + (R - L) >> 1;
  12.     TreeNode node = new TreeNode(nums[mid]);
  13.     node.left = process(nums, L, mid - 1);
  14.     node.right = process(nums, mid + 1, R);
  15.     return node;
  16. }

538.把二叉搜索树转换为累加树⭐

  • 二叉搜索树 —-> 有序
  • 那么有序的元素如果求累加呢？

其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。

  • 从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。
  • 一个变量记录前一个节点的数值 ```java public TreeNode convertBST(TreeNode root) { process(root); return root; }

int pre = 0; //记录前一个节点的数值

//反中序遍历: 按右中左顺序遍历，累加即可 private void process(TreeNode node) { if (node == null) { return; }

  1. process(node.right);  // 右
  2. node.val = node.val + pre;  // 中
  3. pre = node.val;
  4. process(node.left);  // 左

} ```