二叉树

class Node<V> {
  V value;
  Node left;
  Node right;
}

前/中/后序遍历

递归

递归方法比较好理解，前中后序就是分别在上方 1，2，3 对应的位置访问(打印等操作)节点。

public void traverse(Node head) {
  if(head == null) return;
  System.out.println(head.val); // 前序遍历
  traverse(head.left);
  System.out.println(head.val); // 中序遍历
  traverse(head.right);
  System.out.println(head.val); // 后序遍历
}

// 距离 lc.144
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        traverse(root, list);
        return list;
    }

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

迭代

递归转成迭代，核心就是要自己模拟出栈。

前 lc.144

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        TreeNode top = (TreeNode) stack.pop();
        list.add(top.val);
        if (top.right != null) stack.push(top.right);
        if (top.left != null) stack.push(top.left);
    }
    return list;
}

java 的 Stack 是 Vector 的一个子类
java 的 Queue 是由 LinkedList 类实现了 Queue 接口

中 lc.94

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.empty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        TreeNode top = stack.pop();
        list.add(top.val);
        root = top.right;
    }
    return list;
}

后 1c.145

一种方法是，把前序遍历的 stack 依次出栈时不打印，而是装到另一个栈中，最后对另一个栈依次出栈就是后序遍历的结果
另一种方法稍微节约点内存，从上面的二叉树递归序我们知道每个节点有三次遍历到的情况（1 次进入，1 次从左节点返回，1 次从右节点返回），那么，在节点出栈的时候，先判定是否有右节点，如果有的话，就先别出栈了，把右节点入栈；问题是当从右节点再回到这个节点的时候，就需要一个额外变量来确定右侧的节点是否已经访问过了。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode visited = null;
    while (!stack.empty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        TreeNode top = stack.pop();
        if (top.right == null || top.right == visited) {
            list.add(top.val);
            visited = top;
        } else {
            stack.push(top);
            root = top.right;
        }
    }
    return list;
}

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
  if (!root) return []
  const res = []
  const stack = []
  let visited = null
  while (stack.length || root) {
    while (root) {
      stack.push(root)
      root = root.left
    }
    const node = stack.pop()
    if (node.right !== null && node.right !== visited) {
      stack.push(node)
      root = node.right
    } else {
      res.push(node.val)
      visited = node
    }
  }
  return res
}

层序遍历 lc.102

想要实现层序遍历的方法非常多，DFS 也可以，只不过一般不这么用，需要掌握的是 BFS。BFS 的应用非常广泛，其中包括寻找图中的最短路径、解决迷宫问题、树的层序遍历等等。

在遍历过程中，BFS 使用「队列」来存储已经访问的节点，以确保按照广度优先的顺序进行遍历。

/**
 * 如果只是对逐层从上到下从左到右打印出节点，是很容易的，一个queue就解决了。
 * 但是lc102是要返回形如 [[1],[2,3],...] 这样List<List<Integer>>的数据结构，那么就需要两个队列了
 * 当然，（也有更省空间的方法，双指针记住每一层的结尾节点）
 */
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> list = new ArrayList<>();
    if (root == null) return list;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        int size = queue.size(); // 因为queue在变化，所以需要缓存一下size。当然也可以用两个队列，不断交换来实现，那我个人觉得这种方式更好一点。
        for (int i = 0; i < size; i++) {
            TreeNode top = queue.poll();
            level.add(top.val);
            if (top.left != null) queue.offer(top.left);
            if (top.right != null) queue.offer(top.right);
        }
        list.add(level);
    }
    return list;
}

以上都是考验的基础硬编码能力，没什么难的，就是要多练。

特殊二叉树

二叉搜索树

左 < 根 < 右，整体上也是：左子树所有值 < 根 < 右字树所有值。

根据 BST 的特性，判定是否为 BST 的最简单的办法是，中序遍历后，看是否按照升序排序。

/**
 * 判定是否为二叉搜索树 lc.98
 */
class Solution {
    long preValue = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean isLeftValid = isValidBST(root.left);
        if (!isLeftValid) return false; // 注意这里，拿到了左树信息后，就可以及时判断了，当然也可以放到后序的位置做~
        if (preValue == Long.MIN_VALUE) preValue = Long.MIN_VALUE; // // 力扣测试用例里超过了 int 的范围，懂得思想即可
        if (root.val <= preValue) return false;
        preValue = root.val;
        return isValidBST(root.right); // 不在中序立即对左树判断，放到最后也行，return isLeftValid && isValidBST(root.right);
    }
}

这一题非常好，好在可以帮助我们更好的理解当递归中出现返回值的情况：

递归中的 return，是结束当前的调用栈，他并不会阻塞后续的递归栈的执行
每一次 return 的东西是用来看对后续的程序产生的影响，只需在对应的前中后序位置做好逻辑处理即可，具体问题，具体分析

完全二叉树

就是堆那样子的~挨个从上到下，从左到右排列在树中。毫无疑问，很容易联想到层序遍历，问题是怎么判断呢？

当遍历到一个节点没有左节点的时候，它也不应该有右节点
当遍历到一个节点没有右节点的时候，后面所有的节点，都不应该有子节点

/**
 * 判定是否为完全二叉树 lc.958
 */
class Solution {
    public boolean isCompleteTree(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean restShouldBeLeaf = false;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (restShouldBeLeaf && (node.left != null || node.right != null)) {
                return false;
            }
            if (node.left == null && node.right != null) {
                return false;
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (node.right == null) {
                restShouldBeLeaf = true;
            }
        }
        return true;
    }
}

满二叉树

满二叉树，特性：满了，所以深度为 h，则节点数为 2^h - 1。

根据特性去做，很简单，一次 dfs 就能用两个变量统计出深度和节点数。

/**
 * 判定是否为满二叉树
 */
int maxDeep = 0;
int deep = 0;
int count = 0;

public boolean isFullTree(TreeNode root) {
    traverse(root);
    return Math.pow(2, maxDeep) - 1 == count;
}

public void traverse(TreeNode root) {
    if (root == null) return;
    count++;
    deep++;
    maxDeep = Math.max(deep, maxDeep); // 这一步在哪都行，只要在 deep++ 和 deep--之间就都是 ok 的
    traverse(root.left);
    traverse(root.right);
    deep--;
}

平衡二叉树

平衡二叉树的左右子树的高度之差不超过 1，且左右子树也都是平衡的。AVL 树和红黑树都是平衡二叉树，采取了不同的方法自动维持树的平衡。

/**
 * 判定是否为平衡二叉树
 *
 * 定义一个返回体，是需要从左右子树获取的信息
 */
class ReturnType {
    int height;
    boolean isBalance;
    public ReturnType(int height, boolean isBalance) {
        this.height = height;
        this.isBalance = isBalance;
    }
}

public static ReturnType isBalanceTree(TreeNode root) {
    if (root == null) {
        return new ReturnType(0, true);
    }
    /**
     * 第一步，甭管三七二十一，先把递归序写上来
     */
    ReturnType left = isBalanceTree(root.left);
    ReturnType right = isBalanceTree(root.right);
    /**
     * 第二步，需要向左右子树拿信息了。
     */
    int height = Math.max(left.height, right.height);
    boolean isBalance = left.isBalance && right.isBalance && Math.abs(left.height - right.height) <= 1;
    return new ReturnType(height, isBalance);
}

定义好 ReturnType，整个递归的算法就很容易实现了。

二叉树套路技巧

其实经过一部分的训练，可以感受到后序遍历的“魔法了”，后序位置我们可以获取到左子树和右子树的信息，关键在于我们需要什么信息，具体问题，具体分析。由此，可以解决很多问题。

试着把上方没有用树形 DP 方式解决的方法改写成树形 DP。

/**
 * 二叉搜索树判定
 *
 * 思考需要向左右子树获取什么信息：左、右子树是否是 bst，左子树最大值，右子树最小值
 *
 * 好，这里出现了分歧，向左树要最大，向右树要最小，同一个递归中这咋处理？
 *
 * 答案：**合并处理！我全都要~**
 */
class ReturnType {
    boolean isBst;
    int max;
    int min;

    public ReturnType(boolean isBst, int max, int min) {
        this.isBst = isBst;
        this.max = max;
        this.min = min;
    }
}
public boolean isValidBST(TreeNode root) {
    return traverse(root).isBst;
}
public ReturnType traverse(TreeNode root) {
    if (root == null) return null; // 有最大最小值的时候 遇到 null 还是返回 null 吧，若是用语言自带的最大最小值处理比较麻烦
    ReturnType l = traverse(root.left);
    ReturnType r = traverse(root.right);
    long min = root.val, max = root.val;
    if (l != null) {
        min = Math.min(min, l.min);
        max = Math.max(max, l.max);
    }
    if (r != null) {
        min = Math.min(min, r.min);
        max = Math.max(max, r.max);
    }
    boolean isBst = true;
    if (l != null && (!l.isBst || l.max >= root.val)) {
        isBst = false;
    }
    if (r != null && (!r.isBst || r.min <= root.val)) {
        isBst = false;
    }
    return new ReturnType(isBst, min, max);
}

上方的写法其实还可以更简化，这么写是为了更好理解递归里的最优子结构。

/**
 * 满二叉树判定 ReturnType(nodes, deep)
 */
public ReturnType traverse(TreeNode root) {
    if (root == null) return new ReturnType(0, 0);
    ReturnType l = traverse(root.left);
    ReturnType r = traverse(root.right);
    int nodes = l.nodes + r.nodes + 1;
    int deep = Math.max(l.deep, r.deep) + 1;
    return new ReturnType(nodes, deep);
}
public boolean isFullTree(TreeNode root) {
    ReturnType res = traverse(root);
    System.out.println(res);
    return Math.pow(2, res.height) - 1 == res.nodes;
}

注意，还是那句话，具体问题具体分析，这种技巧，并不适合每种二叉树的问题，比如，一颗树，让你求整个树的中位数，树形 DP 的方式就做不到，其实就是没有最优子结构。无法进行分解子问题然后进行后序树形 dp 的问题，就只能进行遍历解决，这种一般运用「回溯」的算法思想。

练习

lc.104 二叉树的最大深度 easy

题简单，思想很重要。

方法一：深度优先遍历，回溯

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (root == null) return 0
  let deep = 0
  let maxDeep = 0
  const traverse = (root) => {
    if (root == null) return
    deep++
    maxDeep = Math.max(maxDeep, deep)
    traverse(root.left)
    traverse(root.right)
    deep--
  }
  traverse(root)
  return maxDeep
}

方法二：分解为子问题，树形 DP

var maxDepth = function (root) {
  const traverse = (root) => {
    if (root == null) return 0
    const left = traverse(root.left)
    const right = traverse(root.right)
    // 当前节点的最大深度为 左右较大的高度加上自身的 1
    return Math.max(left, right) + 1
  }
  return traverse(root)
}

lc.543 二叉树的直径 easy

思考：dfs 遍历好像没啥好办法，但是如果分解为子问题，就很简单了，无非就是左边最长加上右边最长嘛~

/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
  if (root == null) return 0
  let res = 0
  const traverse = (root) => {
    if (root == null) return 0
    const l = traverse(root.left)
    const r = traverse(root.right)
    res = Math.max(l + r, res) // 就是左右子树最大深度之和，保证最大
    return Math.max(l, r) + 1
  }
  traverse(root)
  return res
}

lc.226 翻转二叉树 easy

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
  if (root == null) return null
  let p = root
  const traverse = (root) => {
    if (root == null) return null
    const l = traverse(root.left)
    const r = traverse(root.right)
    root.right = l
    root.left = r
    return root
  }
  traverse(p)
  return root
}

lc.114 二叉树展开为链表

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
  if (root == null) return null
  const traverse = (root) => {
    if (root == null) return null
    let l = traverse(root.left)
    let r = traverse(root.right)
    if (l) {
      root.left = null
      root.right = l
      // 没啥难度就是注意拼接过去的时候可能是一个链表
      while (l.right) {
        l = l.right
      }
      l.right = r
    }
    return root
  }
  traverse(root)
}

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

观察发现这道题，左右子树的操作都不一样，所以用分解问题的方式没什么思路。

那么遍历呢？那就比较简单了，就是把 root.left -> root.right, root.right -> 兄弟节点的 left，关键就在于这一步怎么做。

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function (root) {
  if (root == null) return root
  const traverse = (left, right) => {
    if (left == null || right == null) return
    left.next = right
    traverse(left.left, left.right)
    traverse(right.left, right.right)
    traverse(left.right, right.left)
  }
  traverse(root.left, root.right)
  return root
}

官解中，是根据父节点的 next 指针去获取到父节点的兄弟节点。

lcr.143 子结构判断

/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function (A, B) {
  if (A == null || B == null) return false
  return traverse(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
}

function traverse(nodeA, nodeB) {
  if (nodeB === null) return true
  if (nodeA === null || nodeA.val !== nodeB.val) return false
  const leftOk = traverse(nodeA.left, nodeB.left)
  const rightOk = traverse(nodeA.right, nodeB.right)
  return leftOk && rightOk
}

这道题还是挺有意义的，我一开始写 traverse 函数的时候就陷进去了，老想的先找到 A === B 的节点之后再开始一一比对，实际上可以通过 isSubStructure(A.left, B) 和 isSubStructure(A.right, B) 来巧妙地处理，只要有一个返回了 true，那么就是 ok 的。

力扣大佬题解，写的不错

构造类的问题，一般都是使用分解子问题的方式去解决，一个树 = 根+构造左子树+构造右子树。

lc.654 最大二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function (nums) {
  const build = (l, r) => {
    if (l > r) return null
    let maxIndex = l
    for (let i = l + 1; i <= r; ++i) {
      if (nums[i] > nums[maxIndex]) maxIndex = i
    }
    const node = new TreeNode(nums[maxIndex])
    node.left = build(l, maxIndex - 1)
    node.right = build(maxIndex + 1, r)
    return node
  }
  return build(0, nums.length - 1)
}

按照题目要求，很容易完成，但是此题的最优解是「单调栈」。。。我的天哪，题目不是要递归地构建嘛，这谁想得到啊 😂

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

前序遍历，第一个节点是根节点
中序遍历，根节点左侧为左树，右侧为右树

两者结合，中序从前序中确定根节点，前序根据中序根节点分割取到左侧有子树的 size。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  // 缓存中序的索引
  const map = new Map()
  for (let i = 0; i < inorder.length; ++i) {
    map.set(inorder[i], i)
  }
  const build = (pl, pr, il, ir) => {
    if (pl > pr) return null // 一定注意不要忘记递归结束条件。。。

    const rootVal = preorder[pl]
    const node = new TreeNode(rootVal)

    const inIndex = map.get(rootVal)
    const leftSize = inIndex - il
    node.left = build(pl + 1, pl + leftSize, il, inIndex - 1)
    node.right = build(pl + leftSize + 1, pr, inIndex + 1, ir)
    return node
  }
  return build(0, preorder.length - 1, 0, inorder.length - 1)
}

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

与 lc.105 逻辑一样

/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function (inorder, postorder) {
  const map = new Map()
  for (let i = 0; i < inorder.length; ++i) {
    map.set(inorder[i], i)
  }
  const build = (pl, pr, il, ir) => {
    if (pl > pr) return null

    const rootVal = postorder[pr]
    const node = new TreeNode(rootVal)

    const inIndex = map.get(rootVal)
    const leftSize = inIndex - il
    node.left = build(pl, pl + leftSize - 1, il, inIndex - 1)
    node.right = build(pl + leftSize, pr - 1, inIndex + 1, ir)
    return node
  }

  return build(0, postorder.length - 1, 0, inorder.length - 1)
}

lc.889 根据前序和后序遍历构造二叉树

一个头是根，一个尾是根，无法通过根节点来区分左右子树了，但是仔细观察后，可以使用 pre 的左子树的第一个节点来区分。

/**
 * @param {number[]} preorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var constructFromPrePost = function (preorder, postorder) {
  const map = new Map()
  for (let i = 0; i < postorder.length; ++i) {
    map.set(postorder[i], i)
  }

  const build = (pl, pr, tl, tr) => {
    if (pl > pr) return null
    if (pl === pr) return new TreeNode(preorder[pl]) // ! 这个关键点很容易漏掉, 只有一个节点的时候

    const rootVal = preorder[pl]
    const root = new TreeNode(rootVal)

    const leftRootVal = preorder[pl + 1] // 这里很可能会越界，所以上方需要单独判断 pl == pr 的情况
    const leftRootIndex = map.get(leftRootVal)
    const leftSize = leftRootIndex - tl + 1

    root.left = build(pl + 1, pl + leftSize, tl, leftRootIndex)
    root.right = build(pl + leftSize + 1, pr, leftRootIndex + 1, tr - 1)
    return root
  }
  return build(0, preorder.length - 1, 0, postorder.length - 1)
}

前序+后序还原的二叉树不唯一，比如一直左子树和一直右子树的前后序遍历结果是一样的。

LCR.152 验证二叉搜索树的后序遍历序列

二叉搜索树：左 > 根 > 右，然而给出的是后序的遍历，最右边为根，观察归纳：从左往右第一个大于根的为右子树，并且其后都应当大于根，由此找到突破口。

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyTreeOrder = function (postorder) {
  if (postorder.length <= 1) return true

  const justify = (l, r) => {
    if (l >= r) return true

    const root = postorder[r]

    let i = l
    while (postorder[i] < root) i++
    let j = i
    while (j < r) {
      if (postorder[j++] < root) return false
    }

    return justify(l, i - 1) && justify(i, r - 1)
  }

  return justify(0, postorder.length - 1)
}

力扣不错的解

lc.297 二叉树序列化和反序列化

/**
 * Encodes a tree to a single string.
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  const traverse = (root) => {
    if (root == null) return '#_'
    let str = root.val + '_'
    str += traverse(root.left)
    str += traverse(root.right)
    return str
  }
  return traverse(root)
}

/**
 * Decodes your encoded data to tree.
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  const arr = data.split('_')
  const generate = (arr) => {
    const val = arr.shift() // 每次弹出，对剩下的递归建树
    if (val === '#') return null
    const node = new TreeNode(val)
    node.left = generate(arr)
    node.right = generate(arr)
    return node
  }
  return generate(arr)
}
/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

lc.652 寻找重复的子树

常规能想到的方法就是序列化，为了保证能区分结构，使用 (,) 来进行序列化。

var findDuplicateSubtrees = function (root) {
  const map = new Map()
  const res = new Set()
  const dfs = (node) => {
    if (!node) {
      return ''
    }
    let str = ''
    str += node.val
    str += '('
    str += dfs(node.left)
    str += ')('
    str += dfs(node.right)
    str += ')'
    if (map.has(str)) {
      res.add(map.get(str))
    } else {
      map.set(str, node)
    }
    return str
  }
  dfs(root)
  return [...res]
}

这道题有个技巧是使用 --- 三元组 (长见识了 😭)

var findDuplicateSubtrees = function (root) {
  const map = new Map()
  const res = new Set()
  let idx = 0 // 关键点
  const dfs = (node) => {
    if (!node) {
      return 0
    }
    const tri = [node.val, dfs(node.left), dfs(node.right)] // 三元数组 [根节点的值，左子树序号，右子树序号]
    const hash = tri.toString() // 相同的字数 三元数组完全一样
    if (map.has(hash)) {
      const pair = map.get(hash)
      res.add(pair[0]) //
      return pair[1] //
    } else {
      map.set(hash, [node, ++idx]) //
      return idx
    }
  }
  dfs(root)
  return [...res]
}
// https://leetcode.cn/problems/find-duplicate-subtrees/solutions/1798953/xun-zhao-zhong-fu-de-zi-shu-by-leetcode-zoncw

lc.236 最低公共祖先

常用的 git merge 用的就是这题原理。

var lowestCommonAncestor = function (root, p, q) {
  let ans = null
  const dfs = (node) => {
    if (node == null) {
      return false
    }
    const leftRes = dfs(node.left)
    const rightRes = dfs(node.right)
    // 更容易理解的做法，向左右子树要信息，定义 dfs 返回是否含有 p 或 q
    if (
      (leftRes && rightRes) ||
      ((node.val == p.val || node.val == q.val) && (leftRes || rightRes))
    ) {
      ans = node
      return
    }
    if (node.val == p.val || node.val == q.val || leftRes || rightRes) {
      return true
    }
    return false
  }
  dfs(root)
  return ans
}

// 更加抽象的代码
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  const traverse = (root) => {
    if (root === null) return null
    if (root == p || root == q) return root
    const left = traverse(root.left)
    const right = traverse(root.right)
    if (left && right) return root
    return left ? left : right
  }
  return traverse(root)
}

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

BST 一般都要充分利用它的特性。

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  let res = root
  while (true) {
    if (p.val > res.val && q.val > res.val) {
      res = res.right
    } else if (p.val < res.val && q.val < res.val) {
      res = res.left
    } else {
      break
    }
  }
  return res
}

lc.285 二叉树中序后继节点

这道题被力扣设为 vip 题目了，可以看 lcr053。

顾名思义，最简单的，根据题意中序遍历即可得到答案：

var inorderSuccessor = function (root, p) {
  const stack = []
  let nextIsRes = false
  while (stack.length || root) {
    while (root) {
      stack.push(root)
      root = root.left
    }
    const node = stack.pop()
    if (nextIsRes) return node
    if (node == p) nextIsRes = true
    if (node.right) root = node.right
  }
  return null
}

但是面试怎么可能这么简单呢，挑选候选人，当然需要更优解，因此需要探索到新的思路

节点有右侧节点，那么根据中序规则，后继节点是右侧节点的最左边的子节点
节点无右侧节点，那么根据中序规则，后续节点是父节点中第一个作为左子节点的节点

另外，如果遇上了 BST，则往往有需要利用上 BST 的性质

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @return {TreeNode}
 */
var inorderSuccessor = function (root, p) {
  if (p.right) {
    let p1 = p.right
    while (p1 && p1.left) {
      p1 = p1.left
    }
    return p1
  }
  let res = null
  let p1 = root
  while (p1) {
    if (p1.val > p.val) {
      res = p1
      p1 = p1.left
    } else {
      p1 = p1.right
    }
  }
  return res
}

拓展姊妹题：假设每个节点有一个 parent 指针指向父节点，怎么找后继节点？原理基本一样，不做过多介绍。

接下来是二叉搜索树的相关题目

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

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (root, k) {
  let res
  const dfs = (root) => {
    if (root === null) return
    dfs(root.left)
    if (--k == 0) res = root.val
    dfs(root.right)
  }
  dfs(root)
  return res
}

这道题很简单的利用了 BST 的性质，但是每次查找 k 都是要从头找，频繁查找的效率比较低下。进阶的做法就是记录下每个节点在当前树中的位置，根据目标与节点的大小比较来决定向左树查还是向右树找。频繁查找的优化见「官解」

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

观察发现累加的顺序和中序遍历正好相反，那就很简单啦~

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function (root) {
  let newRoot = root
  const stack = []
  let newVal = 0
  while (stack.length || root) {
    while (root) {
      stack.push(root)
      root = root.right
    }
    const node = stack.pop()
    newVal += node.val
    node.val = newVal
    if (node.left) root = node.left
  }
  return newRoot
}
// 递归的中序反向就更简单啦，先 right，再 left 即可
// 这题与 lc.1038 题目相同

然而这道题的考点是「Morris 遍历」，又又又涨新知识啦 😭Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减 上方的时间空间复杂度都是 O(n)，用了莫里斯遍历后，空间复杂度可以降到 O(1) 水平。

Morris 遍历是一种不使用递归或栈的树遍历算法。在这种遍历中，通过创建链接作为后继节点，使用这些链接打印节点。最后，将更改恢复以恢复原始树。

// 先看一个正常的 Morris 中序遍历，说白了，之前是用栈来让我们从左回到根，
// Morris 只是利用了二叉树自身的指针，来达到从左回到根的操作。
function morrisInorder(root) {
  let curr = root
  let res = []

  while (curr !== null) {
    // 没有左树，直接输出当前节点，并且走向右树
    // 当建立了 新的连接后，也可能是向后回退到根节点的操作
    if (curr.left === null) {
      res.push(curr.val)
      curr = curr.right
    } else {
      // 有左树就走到下一层左树，然后迭代找到左树的最右子树节点，这里判断 !== curr 是因为后面建立了连接
      let temp = curr.left
      while (temp.right !== null && temp.right !== curr) {
        temp = temp.right
      }

      if (temp.right === null) {
        /** 在这里输出则就是前序了 */
        temp.right = curr // 建立连接，比如题目中的 3 --> 4
        curr = curr.left
      } else {
        temp.right = null // 恢复原树，断开连接，比如从 0 回到到 1 时，0.right 指向 1
        res.push(curr.val) // 中序输出
        curr = curr.right // 退回父节点
      }
    }
  }
  return res
}
/** 后序的 Morris 略微复杂一点点 */
function morrisPostorder(root) {
  let reverseOutput = []
  let curr = root

  while (curr !== null) {
    if (curr.right === null) {
      //判断右是否为空
      reverseOutput.push(curr.val)
      curr = curr.left
    } else {
      let temp = curr.right
      while (temp.left !== null && temp.left !== curr) {
        // 寻找左尽头
        temp = temp.left
      }

      if (temp.left === null) {
        reverseOutput.push(curr.val)
        temp.left = curr // 连接左尽头到当前节点
        curr = curr.right
      } else {
        temp.left = null
        curr = curr.left
      }
    }
  }
  // Reverse the output array to get the correct postorder traversal
  return reverseOutput.reverse() // 最终还得反转一下
}

那么这道题，是中序的反向遍历，那就是 Morris 正常中序遍历的镜像：

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function (root) {
  let curr = root
  let sum = 0
  while (curr !== null) {
    if (curr.right == null) {
      sum += curr.val
      curr.val = sum
      curr = curr.left
    } else {
      let prev = curr.right
      while (prev.left !== null && prev.left !== curr) {
        prev = prev.left
      }

      if (prev.left === null) {
        prev.left = curr
        curr = curr.right
      } else {
        prev.left = null
        sum += curr.val
        curr.val = sum
        curr = curr.left
      }
    }
  }
  return root
}

lc.98 验证二叉搜索树

在上方已经做过了，最简单的就是中序遍历的结果是否为升序。

var isValidBST = function (root) {
  let res = true
  let pre = -Infinity
  const traverse = (root) => {
    if (!root) return
    traverse(root.left)
    if (root.val <= pre) {
      res = false
      return
    } else {
      pre = root.val
    }
    traverse(root.right)
  }
  traverse(root)
  return res
}

lc.700 二叉搜索树中的搜索 easy

没啥难度，根据 BST 的性质进行左右半区搜索即可。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function (root, val) {
  if (root === null) return null
  while (root) {
    if (root.val === val) return root
    root = val > root.val ? root.right : root.left
  }
  return null
}

lc.701 二叉搜索树中的插入操作

二叉树的「改」类似于构造，如过用递归遍历的函数需要返回 TreeNode 类型。

先来看下迭代的做法，比较简单，就是找到它合适的位置后，插入即可，由于 BST 的特性，插入的数字一定可以走到叶节点。

/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function (root, val) {
  if (root === null) return new TreeNode(val)
  let p = root
  while (p !== null) {
    if (p.val < val) {
      if (p.right === null) {
        p.right = new TreeNode(val)
        break
      }
      p = p.right
    } else {
      if (p.left === null) {
        p.left = new TreeNode(val)
        break
      }
      p = p.left
    }
  }
  return root
}

var insertIntoBST = function (root, val) {
  // 递归做法
  if (root === null) return new TreeNode(val)
  if (root.val < val) {
    root.right = insertIntoBST(root.right, val) // 往右树里加
  } else {
    root.left = insertIntoBST(root.left, val) // 往左树里加
  }
  return root
}

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

插入是直接加在了叶节点，删除操作会对结构产生变化，需要进行不同情况的判断：

删除节点没有左右子树，直接删除
有一个子树，返回有的那个子树即可
左右子树都有，这就比较麻烦了，它需要把左子树的最大值或者右子树的最小值替换到被删的节点处

/**
 * 迭代法，比较容易出错，最好是同时画图，不然很容易漏掉一些指针操作
 * /
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function (root, key) {
  if (root === null) return null
  let p = root,
    parent = null
  while (p && p.val !== key) {
    parent = p
    if (key < p.val) {
      p = p.left
    } else {
      p = p.right
    }
  }

  if (p == null) return root // 没找到 key
  if (p.left === null && p.right === null) {
    p = null
  } // key 在叶节点，直接删
  /** 如果没有 parent 指针，这后面逻辑走不下去 */
  else if (p.left === null) {
    p = p.right
  } else if (p.right === null) {
    p = p.left
  } else if (p.left && p.right) {
    // 和堆排序的操作类似，核心：找到左子树最大值或者右子树最小值和 p 交换即可
    let r = p.right,
      rp = p
    // 找到右树最小节点
    while (r.left) {
      rp = r
      r = r.left
    }

    /**
     * 断掉 右树最小节点的父指针
     *
     * 个人建议： 这块最好多画画图，脑补确实不易 [捂脸]
     */
    // 压根没有左树节点
    if (rp.val === p.val) {
      rp.right = r.right
    } else {
      // 有左子树节点，那么 r 的右侧节点应当在 rp 的左树
      rp.left = r.right
    }

    // 这里好理解，把右树最小节点和删除节点交换
    r.right = p.right
    r.left = p.left
    p = r
  }

  // 删除的是根节点
  if (parent === null) return p
  // 把新的 P 节点重新连接
  if (parent.left && parent.left.val === key) {
    parent.left = p
  } else {
    parent.right = p
  }
  return root
}

迭代法，通过指针操作，有很多需要注意的点，相比较之下，递归做起来就比较容易了。

/**
 *  再次提醒 --- 递归千万不要套进去，再就是定义好 出参/入参/结束条件， 其他都好说，都好说~
 *
 *  定义： 返回删除树 root 中 key 后的根节点 root
 */
var deleteNode = function (root, key) {
  if (root === null) return null
  if (root.val === key) {
    if (root.left === null) return root.right
    if (root.right === null) return root.left

    // 否则和迭代一样，找左树最大值或右树最小值来替换删除的节点
    let r = root.right
    while (r.left) {
      r = r.left
    }
    // 断开右树最小值的连接
    root.right = deleteNode(root.right, r.val)
    // 交换节点
    r.left = root.left
    r.right = root.right
    root = r
  } else if (root.val < key) {
    root.right = deleteNode(root.right, key)
  } else if (root.val > key) {
    root.left = deleteNode(root.left, key)
  }
  return root
}

lc.95 不同的二叉搜索树 II

这个题目一看就是穷举的问题，穷举~~~暴力递归 yyds！！！由于 BST 的性质，而不用去回溯。

另外，涉及到数组构造树，一般会使用「区间指针」去构造。

/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  // if(n == 1) return new TreeNode(n)
  /**
   * 定义递归： 输入：区间 [l..r]，输出： TreeNode[]
   * 结束条件： l > r
   *
   */
  const build = (l, r) => {
    const res = []
    if (l > r) {
      res.push(null) // 注意要加入空节点,易错
      return res
    }
    // 穷尽枚举
    for (let i = l; i <= r; ++i) {
      const left = build(l, i - 1)
      const right = build(i + 1, r)
      for (const l of left) {
        for (const r of right) {
          const root = new TreeNode(i)
          root.left = l
          root.right = r
          res.push(root)
        }
      }
    }

    return res
  }

  return build(1, n)
}

lc.96 不同的二叉搜索树

做了 lc.95 那么这道题的思路还是挺容易的。这种穷尽枚举的题目，一般使用递归解决。因为是 BST，所以利用 bst 的性质即可，而不用去回溯。

/**
 * 这道题需要注意的是，需要加 「备忘录」，否则会超时~
 */
var numTrees = function (n) {
  const memo = Array.from(Array(n + 1), () => Array(n + 1).fill(0))
  /**
   * 定义递归: 输入：区间 [l..r], 输出：不同的个数 number
   * 结束条件：l > r, return 1
   */
  const build = (l, r) => {
    let res = 0
    if (l > r) return 1
    if (memo[l][r]) return memo[l][r]

    for (let i = l; i <= r; i++) {
      const left = build(l, i - 1)
      const right = build(i + 1, r)
      res += left * right
    }

    memo[l][r] = res
    return res
  }
  return build(1, n)
}

当然啦，这道题用动态规划去做，时间复杂度空间复杂度都会更低一点，详细见官解，另外官解给出了这道题的奥义「卡塔兰数」，又又又长知识啦~~~~

/**
 * dp
 */
var numTrees = function (n) {
  // 定义 dp[i] 表示 [1..i] 的二叉搜索树数量
  const dp = new Array(n + 1).fill(0)
  dp[0] = 1
  dp[1] = 1

  for (let i = 2; i <= n; ++i) {
    for (let j = 1; j <= i; ++j) {
      dp[i] += dp[j - 1] * dp[i - j] // 一个根节点,左子树的个数*右子树的个数就是当前根组合出的个数
    }
  }
  return dp[n]
}
/**
 * 卡塔兰数
 */
var numTrees = function (n) {
  let C = 1
  for (let i = 0; i < n; ++i) {
    C = (C * 2 * (2 * i + 1)) / (i + 2)
  }
  return C
}

总的来说，二叉树的问题，还是很有意思的，同时对指针迭代和递归思想的培养很有效，需要多思考，另外基础的操作需要多练习。