Easy

501. 二叉搜索树中的众数

572. 另一棵树的子树

404. 左叶子之和

270. 最接近的二叉搜索树值

遍历二叉树

94. 二叉树的中序遍历

迭代法

  1. public List<Integer> inorderTraversal(TreeNode root) {
  2.     List<Integer> ret = new ArrayList<>();
  3.     Stack<TreeNode> stack = new Stack<>();
  4.     TreeNode curr = root;
  5.     while (curr != null || !stack.isEmpty()){
  6.         // go to leftmost
  7.         while (curr != null){
  8.             stack.push(curr);
  9.             curr = curr.left;
  10.         }
  11.         // the top of stack's left part has been traversed
  12.         curr = stack.pop();
  13.         ret.add(curr.val);
  14.         // next step -> go to check the right node
  15.         curr = curr.right;
  16.     }
  18.     return ret;
  19. }

144. 二叉树的前序遍历(不熟练)

迭代法

  1. public List<Integer> preorderTraversal(TreeNode root) {
  2.     List<Integer> ret = new ArrayList<>();
  3.     // root
  4.     // func(root.left)
  5.     // func(root.right)
  6.     Stack<TreeNode> stack = new Stack<>();
  7.     TreeNode curr = root;
  8.     while (!stack.isEmpty() || curr != null){
  9.         while (curr != null){
  10.             ret.add(curr.val);
  11.             stack.push(curr);
  12.             curr = curr.left;
  13.         }
  14.         curr = stack.pop().right;
  15.     }
  16.     return ret;
  17. }

145. 二叉树的后序遍历

迭代法

  • 先一直向左搜索同时入栈，直到空为止。

  • 弹出栈顶元素（我们知道左子树都搜索完成，但是不知右子树是否搜索完成）

    • 如果没有右节点，则搜索完成 或者 有右节点但是已经搜索完成了（通过之前保存搜索完成的节点，我们判断该右节点是否被搜索过）
      • 保存该搜索完成的节点
      • 我们设下个搜索的节点为空

    • 其他情况

      • 我们下个循环搜索右节点 ```java public List postorderTraversal(TreeNode root) { List res = new ArrayList(); if (root == null) { return res; }

      Deque stack = new LinkedList(); TreeNode prev = null; // 对于每个节点进行搜索 while (root != null || !stack.isEmpty()) { // 一直向左搜索，直达为空 while (root != null) {

      1.    stack.push(root);
      2.    root = root.left;

      } // 弹出栈顶 root = stack.pop(); // 如果右节点为空或者右节点已经搜索过了，则该节点关闭 // 解释：因为右节点会在root之后的下一个入栈，如果右节点已经搜索过 // 则会被保存在上一个关闭的节点（prev）中，我们可以将此作为右节点是否 // 搜索过的条件。 if (root.right == null || root.right == prev) {

      1.    res.add(root.val);
      2.    // 保存该节点为上一个关闭的节点
      3.    prev = root;
      4.    root = null;

      } else {

      1.    // 继续搜索右节点
      2.    stack.push(root);
      3.    root = root.right;

      } } return res; } ```

      构造二叉树

      规律：

  • 根据前序遍历的第一个节点或者后序遍历的第一个节点是根节点的性质

  • 去中序遍历找出左子树和右子树
  • 利用左子树的长度再去分割前序遍历或者后序遍历

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

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

  1. 不是很熟练，index写的迷迷糊糊的。

    1008. 前序遍历构造二叉搜索树

    复习：

  2. 不是很熟练，错误的想到了二分法 -> 只需线性查找左子树最后一个元素即可

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

路径（Path）

技巧：

  • 利用前缀和，将每个node作为路径的终点
  • 这个题型属于自上而下构造答案

    112. 路径总和（不熟练）

    复习：

  1. 结果：不熟练，在碰到叶子结点就需要返回了，不然无法处理根节点为空的情况。

    113. 路径总和 II

    复习：

  2. 结果 -> OK，五分钟熟练写出来

    437. 路径总和 III(不熟练)

    复习：

  3. 结果 -> OK，十分钟熟练写出来，记得很清楚。前缀和+HashMap+把每个node作为路径终点。

    687. 最长同值路径（不熟练）

    答案：自下而上的后序遍历+全局变量+递归

公共祖先**

235. 二叉搜索树的最近公共祖先 (不熟练)

答案：迭代遍历二叉搜索树，如果全大于当前节点往右，全小于往左，其他情况则表示这是分岔点，也就是最深的公共祖先了。

236. 二叉树的最近公共祖先 (不熟练)

答案：后序遍历+全局变量+最近公共祖先唯一存在且有两种判断方法

  1. left和right分别包含两个节点
  2. 当前节点是p或q中的一个，并且他的左或右子树包含另一个节点

Next指针**

116. 填充每个节点的下一个右侧节点指针(不熟练)

答案：两个while循环，外循环一层层往下，内循环对于一层的内每个节点连接它的下一层。

**117. 填充每个节点的下一个右侧节点指针 II(不熟练)

答案：使用DummyHead来连接下一层，因为不能确定左右孩子的存在情况，所以下一层按照出现顺序串起来。

自底向上

543. 二叉树的直径

答案：后续遍历+全部变量

236. 二叉树的最近公共祖先

复习

  1. 十分钟做出来了，和之前的思路一模一样。写一个辅助函数，后续遍历的去检查包含性。关键是要记得检查本节点包含的可能性。

    自上而下

    226. 翻转二叉树

    复习：

  2. OK，十分熟练

    101. 对称二叉树

    复习：

  3. OK，十分熟练

前缀和

层序遍历

199. 二叉树的右视图

103. 二叉树的锯齿形层序遍历

复习

  1. 自己是做出来了，15分钟。就是有些不熟练了，怎么去zigzag。规律应该是：上一层给我的一直都是反顺序的，所以我一直倒着走，然后我给下一层的也是反顺序的。

    Tricky Problems

    剑指 Offer 36. 二叉搜索树与双向链表

    98. 验证二叉搜索树(不会)

    复习：

  2. 就是中序遍历+保存前一个节点的值为全局变量(记得使用long来解决溢出问题)。

    114. 二叉树展开为链表

    复习

  3. 就是前序遍历+保存前一个节点为全局变量。

    450. 删除二叉搜索树中的节点（不会）

    答案:

  • 利用搜索二叉树的属性，从而定位搜索左子树还是右子树
  • 搜索到后
    • 如果左子树不为空，则用前一个（precedessor）代替，然后去左子树递归删除precedessor
    • 如果右子树不为空，则用后一个（successor）代替，然后去右子树递归删除successor
    • 若为叶子节点，则返回null

863. 二叉树中所有距离为 K 的结点（太难了，学不会，理解不了）

复习

  1. 这题没学会。但是频率不高，就偷懒了。

    230. 二叉搜索树中第K小的元素

    答案优化 中序遍历 + 全局变量记录是第几大的元素、

    776. 拆分二 叉搜索树