15. 不同的二叉搜索树II

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();

} }

};

15. 不同的二叉搜索树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 种不同结构的二叉搜索树：

13321

递归创建子树

/**

• @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++) { // 左子树集

// 右子树无法共享，但可以借用节点个数相同的树，每个节点增加一个偏移量 node.right = clone(rightNode, j);

dp[i].push(node);

} }

} }

return dp[n];

};