二叉树的遍历¶

前序遍历¶

示例:

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

来源: LeetCode第144题

递归方式¶

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  let arr = [];
  let traverse = (root) => {
    if(root == null) {
      return;
    }
    arr.push(root.val);
    traverse(root.left);
    traverse(root.right); 
  }
  traverse(root);
  return arr;
};

非递归方式¶

var preorderTraversal = function(root) {
  if(root == null) {
    return [];
  }
  let stack = [], res = [];
  stack.push(root);
  while(stack.length) {
    let node = stack.pop();
    res.push(node.val);
    // 左子树后进先出，进行先左后右的深度优先遍历
    if(node.right) {
      stack.push(node.right);
    }
    if(node.left) {
      stack.push(node.left);
    }
  }
  return res;
};

中序遍历¶

给定一个二叉树，返回它的中序遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [1,3,2]

来源: LeetCode第94题

递归方式:¶

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  let arr = [];
  let traverse = (root) => {
    if (root == null) {
      return;
    }
    traverse(root.left);
    arr.push(root.val);
    traverse(root.right); 
  }
  traverse(root);
  return arr;
};

非递归方式¶

var inorderTraversal = function(root) {
  if(root == null) return [];
  let stack = [], res = [];
  let p = root;
  while(stack.length || p) {
    while(p) {
      stack.push(p);
      p = p.left;
    }
    let node = stack.pop();
    res.push(node.val);
    p = node.right;
  }   
  return res;
};

后序遍历¶

给定一个二叉树，返回它的后序遍历。

示例:

输入: [1,null,2,3]  

   1
    \
     2
    /
   3 

输出: [3,2,1]

来源: LeetCode第145题

递归方式¶

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
  let arr = [];
  let traverse = (root) => {
    if(root == null) return;
    traverse(root.left);
    traverse(root.right);
    arr.push(root.val);
  }
  traverse(root);
  return arr
};

非递归方式¶

var postorderTraversal = function(root) {
  if(root == null) return [];
  let stack = [], res = [];
  let visited = new Set();
  let p = root;
  while(stack.length || p) {
    while(p) {
      stack.push(p);
      p = p.left;
    }
    let node = stack[stack.length - 1];
    // 如果右子树存在，而且右子节点未被访问
    if(node.right && !visited.has(node.right)) {
      p = node.right;
      visited.add(node.right);
    } else {
      res.push(node.val);
      stack.pop();
    }
  }
  return res;
};

最大/最小深度¶

最大深度¶

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]：

返回它的最大深度 3 。来源: LeetCode第104题

递归实现¶

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
  // 递归终止条件 
  if(root == null) {
    return 0;
  }
  return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
};

非递归实现¶

采用层序遍历的方式，非常好理解。

var maxDepth = function(root) {
  if(root == null) return 0;
  let queue = [root];
  let level = 0;
  while(queue.length) {
    let size = queue.length;
    while(size --) {
      let front = queue.shift();
      if(front.left) {
        queue.push(front.left);
      }
      if(front.right) {
        queue.push(front.right);
      }
    }
    // level ++ 后的值代表着现在已经处理完了几层节点
    level ++;
  }
  return level;
};

最小深度¶

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7]:

返回它的最小深度 2.

来源: LeetCode第111题

递归实现¶

在实现的过程中，如果按照最大深度的方式来做会出现一个陷阱，即:

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
  // 递归终止条件 
  if(root == null) return 0;
  return Math.min(minDepth(root.left) + 1, minDepth(root.right) + 1);
};

当 root 节点有一个子节点为空的时候，此时返回的是 1，但这是不对的，最小高度指的是**根节点到最近叶子节点**的最小路径，而不是到一个空节点的路径。

因此我们需要做如下的调整:

var minDepth = function(root) {
  if(root == null) {
    return 0;
  }
  // 左右子节点都不为空才能像刚才那样调用
  if(root.left && root.right) {
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
  }
  // 右子节点为空了，直接忽略之
  else if(root.left) {
    return minDepth(root.left) + 1;
  }
  // 左子节点为空，忽略
  else if(root.right) {
    return minDepth(root.right) + 1;
  }
  // 两个子节点都为空，说明到达了叶子节点，返回 1
  else {
    return 1;
  }
};

非递归实现¶

类似于最大高度问题，采用了层序遍历的方式，很容易理解。

var minDepth = function(root) {
  if(root == null) return 0;
  let queue = [root];
  let level = 0;
  while(queue.length) {
    let size = queue.length;
    while(size --) {
      let front = queue.shift();
      // 找到叶子节点
      if(!front.left && !front.right) return level + 1;
      if(front.left) queue.push(front.left);
      if(front.right) queue.push(front.right);
    }
    // level ++ 后的值代表着现在已经处理完了几层节点
    level ++;
  }
  return level;
};

LCA 问题¶

LCA (Lowest Common Ancestor)即最近公共祖先问题。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

二叉树的最近公共祖先¶

对于一个普通的二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

来源: LeetCode第236题

有下面两种解决方法

祖先节点集合法¶

思路一: 首先遍历一遍二叉树，记录下每个节点的父节点。然后对于题目给的 p 节点，根据这个记录表不断的找 p 的上层节点，直到根，记录下 p 的**上层节点集合**。然后对于 q 节点，根据记录不断向上找它的上层节点，在寻找的过程中一旦发现**这个上层节点已经包含在刚刚的集合**中，说明发现了最近公共祖先，直接返回。

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  // 根节点是空；根节点等于目标节点，根节点就是最近公共祖先
  if (root == null || root == p || root == q) {
    return root;
  }
  // 存储节点关系
  let set = new Set();
  let map = new WeakMap();
  let queue = [];
  queue.push(root);
  // 层序遍历
  while(queue.length) {
    let size = queue.length;
    while(size--) {
      let front = queue.shift();
      if (front.left) {
        queue.push(front.left);
        // 记录父节点
        map.set(front.left, front);
      }
      if (front.right) {
        queue.push(front.right);
        // 记录父节点
        map.set(front.right, front);
      }
    }
  }
  // 构造 p 的上层节点集合
  while(p) {
    set.add(p);
    p = map.get(p);
  }
  while(q) {
    // 一旦发现公共节点重合，直接返回
    if(set.has(q)) {
      return q;
    }
    q = map.get(q);
  }
};

可以看到整棵二叉树遍历了一遍，时间复杂度大致是 O(n)，但是由于哈希表的存在，空间复杂度比较高，接下来我们来用另一种遍历的方式，可以大大减少空间的开销。

深度优先遍历法¶

思路二: 深度优先遍历二叉树，如果当前节点为 p 或者 q，直接返回这个节点，否则查看左右子节点，左子节点中不包含 p 或者 q 则去找右子节点，右子节点不包含 p 或者 q 就去找左子节点，剩下的情况就是**左右子节点中都存在 p 或者 q**, 那么此时直接返回这个节点。

代码非常简洁、美观，不过更重要的是体会其中递归调用的过程，代码是自顶向下执行的，我建议大家用**自底向上**的方式来理解它，即从最左下的节点开始分析，相信你会很好的理解整个过程。

var lowestCommonAncestor = function(root, p, q) {
  if (root == null || root == p || root == q) {
    return root;
  }
  let left = lowestCommonAncestor(root.left, p, q);
  let right = lowestCommonAncestor(root.right, p, q);
  if(left == null) {
    return right;
  } else if(right == null) {
    return left;
  }
  return root;
};

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

给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

来源: LeetCode第235题

实现：二叉搜索树作为一种特殊的二叉树，当然是可以用上述的两种方式来实现的。

不过借助二叉搜索树有序的特性，我们也可以写出另外一个版本的深度优化遍历。

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  if(root == null || root == p || root == q) {
    return root;
  }
  // root.val 比 p 和 q 都大，找左子节点
  if(root.val > p.val && root.val > q.val) {
    return lowestCommonAncestor(root.left, p, q);
  }
  // root.val 比 p 和 q 都小，找右子节点
  if(root.val < p.val && root.val < q.val) {
    return lowestCommonAncestor(root.right, p, q);
  }
  else {
    return root;
  }
};

同时也可以采用非递归的方式:

var lowestCommonAncestor = function(root, p, q) {
  let node = root;
  while (node) {
    if (p.val > node.val && q.val > node.val) {
      node = node.right;
    }
    else if (p.val < node.val && q.val < node.val) {
      node = node.left;
    }
    else {
      return node;
    }
  }
};

是不是被二叉树精简而优雅的代码惊艳到了呢？希望你能好好体会其中遍历的过程，然后务必自己独立实现一遍，保证对这种数据结构足够熟悉，增强自己的编程内力。

对称二叉树¶

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

来源: LeetCode第101题

递归实现：递归方式的代码是非常干练和优雅的，希望你先自己实现一遍，然后对比改进。

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
  if (root == null) {
    return true;
  }
  let help = (node1, node2) => {
    // 都为空，是对称的
    if(!node1 && !node2) {
      return true;
    }
    // 一个为空一个不为空，或者两个节点值不相等，都不是对称的
    if(!node1 || !node2 || node1.val !== node2.val) {
      return false;
    }
    // 递归遍历子节点
    return (help(node1.left, node2.right) && help(node1.right, node2.left));
  }
  return help(root.left, root.right);
};

非递归实现：用一个队列保存访问过的节点，每次取出两个节点，进行比较。

var isSymmetric = function(root) {
  if(root == null) {
    return true;
  }
  let queue = [root.left, root.right];
  let node1, node2;
  while(queue.length) {
    node1 = queue.shift();
    node2 = queue.shift();
    // 两节点均为空
    if(!node1 && !node2) {
      continue;
    }
    // 一个为空一个不为空，或者两个节点值不相等
    if(!node1 || !node2 || node1.val !== node2.val) {
      return false;
    }
    queue.push(node1.left);
    queue.push(node2.right);
    queue.push(node1.right);
    queue.push(node2.left);
  }
  return true;
};

二叉树中的路径问题¶

No.1 二叉树的直径¶

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 : 给定二叉树

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

来源: LeetCode第543题

思路¶

所谓的求直径, 本质上是求树中节点左右子树高度和的最大值。

注意，这里我说的是树中节点, 并非根节点。因为会有这样一种情况:

那这个时候，直径最大的路径是: 8 -> 4 -> 2-> 5 -> 6 -> 7。交界的元素并不是根节点。这是这个问题特别需要注意的地方，不然无解。

初步求解¶

目标已经确定了，求树中节点左右子树高度和的最大值。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
  if (root == null) {
    return 0;
  }
  // 辅助函数：求某个节点最大深度
  let maxDepth = (node) => {
    if (node == null) {
      return 0;
    }
    return Math.max(maxDepth(node.left) + 1, maxDepth(node.right) + 1);
  }
  // 辅助函数（递归）
  let help = (node) => {
    if (node == null) {
      return 0;
    }
    let rootSum = maxDepth(node.left) + maxDepth(node.right);
    let childSum = Math.max(help(node.left), help(node.right));
    return Math.max(rootSum, childSum);
  }
  return help(root);
};

这样一段代码放到 LeetCode 是可以通过，但时间上却不让人很满意，为什么呢？

因为在反复调用 maxDepth 的过程，对树中的一些节点增加了很多不必要的访问。比如：

我们看什么时候访问节点 8，maxDepth(节点 2)的时候访问， maxDepth(节点 4)的时候又会访问，如果节点层级更高，重复访问的次数更加频繁，剩下的节点6、节点 7 都是同理。每一个节点访问的次数大概是 O(logK)(设当前节点在第 K 层)。那能不能把这个频率降到 O(1) 呢？

答案是肯定的，接下来我们来优化这个算法。

优化解法¶

var diameterOfBinaryTree = function(root) {
  let max = 0;
  if (root == null) {
    return 0;
  }
  let help = (node) => {
    if (node == null) {
      return 0;
    }
    let left = node.left ? help(node.left) + 1: 0;
    let right = node.right ? help(node.right) + 1: 0;
    let cur = left + right;
    if (cur > max) {
      max = cur; 
    }
    // 这个返回的操作相当关键
    return Math.max(left, right);
  }
  help(root);
  return max;
};

在这个过程中设置了一个max全局变量，深度优先遍历这棵树，每遍历完一个节点就更新max，并通过返回值的方式自底向上把当前节点左右子树的最大高度传给父函数使用，使得每个节点只需访问一次即可。

现在提交我们优化后的代码，时间消耗明显降低。

No.2 二叉树的所有路径¶

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

来源: LeetCode第257题

递归解法¶

利用 DFS(深度优先遍历) 的方式进行遍历。

/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
  let path = [];
  let res = [];
  let dfs = (node) => {
    if (node == null) {
      return;
    }
    path.push(node);
    dfs(node.left);
    dfs(node.right);
    if(!node.left && !node.right) {
      res.push(path.map(item => item.val).join('->'));
    }
    // 注意每访问完一个节点记得把它从path中删除，达到回溯效果
    path.pop();
  }
  dfs(root);
  return res;
};

非递归解法¶

接下来我们通过非递归的后序遍历的方式来实现一下, 顺便复习一下后序遍历的实现。

提示：后序遍历其实也是 DFS 的一种具体实现方式。

var binaryTreePaths = function(root) {
  if (root == null) {
    return [];
  }
  let stack = [];
  let p = root;
  let set = new Set();
  let res = [];
  while(stack.length || p) {
    while(p) {
      stack.push(p);
      p = p.left;
    }
    let node = stack[stack.length - 1];
    // 叶子节点
    if(!node.right && !node.left) {
      res.push(stack.map(item => item.val).join('->'));
    }
    // 右子节点存在，且右子节点未被访问
    if(node.right && !set.has(node.right)) {
      p = node.right;
      set.add(node.right);
    } else {
      stack.pop();
    }
  }
  return res;
};

No.3 二叉树的最大路径和¶

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

来源: LeetCode第124题

解答

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function(root) {
  let help = (node) => {
    if (node == null) {
      return 0;
    }
    let left = Math.max(help(node.left), 0);
    let right = Math.max(help(node.right), 0);
    let cur = left + node.val + right;
    // 如果发现某一个节点上的路径值比max还大，则更新max
    if(cur > max) {
      max = cur;
    }
    // left 和 right 永远是"一根筋"，中间不会有转折
    return Math.max(left, right) + node.val;
  }
  let max = Number.MIN_SAFE_INTEGER;
  help(root);
  return max;
};

二叉搜索树¶

No.1 验证二叉搜索树¶

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

二叉搜索树特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

来源: LeetCode第98题

方法一: 中序遍历¶

通过中序遍历，保存前一个节点的值，扫描到当前节点时，和前一个节点的值比较，如果大于前一个节点，则满足条件，否则不是二叉搜索树。

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
  let prev = null;
  const help = (node) => {
    if (node == null) {
      return true;
    }
    if (!help(node.left)) {
      return false;
    }
    if (prev !== null && prev >= node.val) {
      return false;
    }
    // 保存当前节点，为下一个节点的遍历做准备
    prev = node.val;
    return help(node.right);
  }
  return help(root);
};

方法二: 限定上下界进行DFS¶

二叉搜索树每一个节点的值，都有一个**上界和下界**，深度优先遍历的过程中，如果访问左子节点，则通过当前节点的值来**更新左子节点节点的上界**，同时访问右子节点，则**更新右子节点的下界**，只要出现节点值越界的情况，则不满足二叉搜索树的条件。

  parent
  /    \
left   right

假设这是一棵巨大的二叉树的一个部分(parent、left、right都是实实在在的节点)，那么全部的节点排完序一定是这样:

...left, parent, right...

可以看到左子节点的最严格的上界是该节点, 同时, 右子节点的最严格的下界也是该节点。我们按照这样的规则来进行更新上下界。

递归实现:

var isValidBST = function(root) {
  const help = (node, max, min) => {
    if(node == null) {
      return true;
    }
    if(node.val >= max || node.val <= min) {
      return false;
    }
    // 左子节点更新上界，右子节点更新下界，相当于边界要求越来越苛刻
    return help(node.left, node.val, min) && help(node.right, max, node.val);
  }
  return help(root, Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER);
};

非递归实现:

var isValidBST = function(root) {
  if (root == null) {
    return true;
  }
  let stack = [root];
  let min = Number.MIN_SAFE_INTEGER;
  let max = Number.MAX_SAFE_INTEGER;
  root.max = max;
  root.min = min;
  while(stack.length) {
    let node = stack.pop();
    if(node.val <= node.min || node.val >= node.max) {
      return false;
    }
    if(node.left) {
      stack.push(node.left);
      // 更新上下界
      node.left.max = node.val;
      node.left.min = node.min;
    }
    if(node.right) {
      stack.push(node.right);
      // 更新上下界
      node.right.max = node.max;
      node.right.min = node.val;
    }
  }
  return true;
};

No.2 有序数组转换为二叉搜索树¶

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

来源: LeetCode第108题

实现

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
  let help = (start, end) => {
    if(start > end) return null;
    if(start === end) return new TreeNode(nums[start]);
    let mid = Math.floor((start + end) / 2);
    // 找出中点建立节点
    let node = new TreeNode(nums[mid]);
    node.left = help(start, mid - 1);
    node.right = help(mid + 1, end);
    return node;
  }
  return help(0, nums.length - 1);
};

递归程序比较好理解，不断地调用 help 完成整棵树树的构建。那如何用非递归来解决呢？我觉得这是一个非常值得大家思考的问题。希望你能动手试一试，如果实在想不出来，可以参考下面我写的非递归版本。

其实思路跟递归的版本是一样的，只不过实现起来是用栈来实现 DFS 的效果。

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
  if(nums.length === 0) return null;
  let mid = Math.floor(nums.length / 2);
  let root = new TreeNode(nums[mid]);
  // 说明: 
  // 1. index 指的是当前元素在数组中的索引 
  // 2. 每一个节点的值都是区间中点，那么 start 属性就是这个区间的起点，end 为其终点
  root.index = mid; root.start = 0; root.end = nums.length - 1;
  let stack = [root];
  while(stack.length) {
    let node = stack.pop();
    // node 出来了，它本身包含了一个区间，[start, ..., index, ... end]
    // 下面判断[node.start, node.index - 1]之间是否还有开发的余地
    if(node.index - 1 >= node.start) {
      let leftMid = Math.floor((node.start + node.index)/2);
      let leftNode = new TreeNode(nums[leftMid]);
      node.left = leftNode;
      // 初始化新节点的区间起点、终点和索引
      leftNode.start = node.start;
      leftNode.end = node.index - 1;
      leftNode.index = leftMid;
      stack.push(leftNode);
    }
    // 中间夹着node.index, 已经有元素了，这个位置不能再开发
    // 下面判断[node.index + 1, node.end]之间是否还有开发的余地
    if(node.end >= node.index + 1) {
      let rightMid = Math.floor((node.index + 1 + node.end)/2);
      let rightNode = new TreeNode(nums[rightMid]);
      node.right = rightNode;
      // 初始化新节点的区间起点、终点和索引
      rightNode.start = node.index + 1; 
      rightNode.end = node.end;
      rightNode.index = rightMid;
      stack.push(rightNode);
    }
  }
  return root;
};

No.3 二叉树展开为链表¶

给定一个二叉(搜索)树，原地将它展开为链表。

例如，给定二叉树

将其展开为：

来源: LeetCode第114题

递归方式

采用后序遍历，遍历完左右子节点我们要做些什么呢？用下面的图来演示一下

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
  if (root == null) {
    return;
  }
  flatten(root.left);
  flatten(root.right);
  if (root.left) {
    let p = root.left;
    while(p.right) {
      p = p.right;
    }
    p.right = root.right;
    root.right = root.left;
    root.left = null;
  }
};

非递归方式

采用非递归的后序遍历方式，思路跟之前的完全一样。

var flatten = function(root) {
  if(root == null) return;
  let stack = [];
  let visited = new Set();
  let p = root;
  // 开始后序遍历
  while(stack.length || p) {
    while(p) {
      stack.push(p);
      p = p.left;
    }
    let node = stack[stack.length - 1];
    // 如果右子节点存在，而且右子节点未被访问
    if(node.right && !visited.has(node.right)) {
      p = node.right;
      visited.add(node.right);
    } else {
      // 以下为思路图中关键逻辑
      if(node.left) {
        let p = node.left;
        while(p.right) {
          p = p.right;
        }
        p.right = node.right;
        node.right = node.left;
        node.left = null;
      }
      stack.pop();
    }
  }
};

No.4 不同的二叉搜索树II¶

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

来源: LeetCode第95题

递归解法

递归创建子树

/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function(n) {
  let help = (start, end) => {
    if(start > end) return [null];
    if(start === end) return [new TreeNode(start)];
    let res = [];
    for(let i = start; i <= end; i++) {
      // 左子节点集
      let leftNodes = help(start, i - 1);
      // 右子节点集
      let rightNodes = help(i + 1, end);
      for(let j = 0; j < leftNodes.length; j++) {
        for(let k = 0; k < rightNodes.length; k++) {
          let root = new TreeNode(i);
          root.left = leftNodes[j];
          root.right = rightNodes[k];
          res.push(root);
        }
      }
    }
    return res;
  }
  if(n == 0) return [];
  return help(1, n);
};

非递归解法

var generateTrees = function(n) {
  let clone = (node, offset) => {
    if(node == null) return null;
    let newnode = new TreeNode(node.val + offset);
    newnode.left = clone(node.left, offset);
    newnode.right = clone(node.right, offset);
    return newnode;
  }
  if(n == 0) return [];
  let dp = [];
  dp[0] = [null];
  // i 是子问题中的节点个数，子问题: [1], [1,2], [1,2,3]...逐步递增，直到[1,2,3...,n]
  for(let i = 1; i <= n; i++) {
    dp[i] = [];
    for(let j = 1; j <= i; j++) {
      // 左子树集
      for(let leftNode of dp[j - 1]) {
        // 右子树集
        for(let rightNode of dp[i - j]) {
          let node = new TreeNode(j);
          // 左子树结构共享
          node.left = leftNode;
          // 右子树无法共享，但可以借用节点个数相同的树，每个节点增加一个偏移量
          node.right = clone(rightNode, j);
          dp[i].push(node);
        }
      }
    }
  }
  return dp[n];
};

Last update: May 28, 2021