二叉树
124. 二叉树中的最大路径和
时间复杂度：，其中 是二叉树中的节点个数。 空间复杂度：，其中 是二叉树的高度。 空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。
本题的思路比较简单，用递归的方式进行深度优先搜索，首先获取每个节点的值，然后递归处理左右子树的节点值，得到左右子树的最大路径和，如果子树路径和小于 0，则舍去，否则将子树路径和加到根节点路径和中。在处理完左右子树之后，需要判断当前节点与左右子树构成路径的和是否比当前的最大路径和要大，如果是则更新最大路径和。
题目要求最大路径和，而最大路径不一定经过根节点，因此我们需要考虑最大路径经过某个节点时的情况。对于一个节点，它的最大路径和可以有以下几种情况： 只有该节点自身； 该节点和其左子树； 该节点和其右子树； 该节点、其左子树和右子树。 所以对于一个节点，我们需要计算经过该节点的最大路径和。可以使用递归的方式计算经过每个节点的最大路径和，并同时更新全局最大路径和。
Javascript
var maxPathSum = function (root) {
// 如果都是负数，则选择负数中最小的
// 所以此处不能 初始值为 0
var ans = -Infinity;
// 遍历节点
traverse(root);
return ans;
function traverse(root) {
// 没有子节点的 空节点了，没有路径了
// 所以是 0
if (root == null) {
return 0;
}
// 此处跟 0 做比较，如果是小于0 的 就舍弃，说明，当前节点就是最大的起始路径
// 如果 左右2边 是小于 0 的，可以放弃 该路径
var left = Math.max(0, traverse(root.left));
var right = Math.max(0, traverse(root.right));
// 递归计算过程中，选择计算结果最大的那个值
ans = Math.max(ans, left + root.val + right);
// 选择左右2边 最大的 路径 + 当前的
return Math.max(left, right) + root.val;
}
};
105. 从前序与中序遍历序列构造二叉树
需要注意的是，该方法需要对数组进行切片操作，因此空间复杂度较高。如果希望优化空间复杂度，可以使用两个指针分别指向前序遍历数组和中序遍历数组 的位置，通过指针的移动来模拟切片操作。
这道题可以通过递归实现，递归过程中，每次都从前序遍历中取出根节点，然后从中序遍历中找到该节点的位置，以该位置为分界点将中序遍历分成左子树和右子树两个部分，然后分别对左子树和右子树进行递归，直到子树为空为止。
Javascript
var buildTree = function (preorder, inorder) {
if (preorder.length === 0) {
return null;
}
const rootVal = preorder[0];
const rootIndex = inorder.indexOf(rootVal);
const root = new TreeNode(rootVal);
// inorder 通过rootIndex 划分为左右子树 ，左子树有 rootIndex 个元素
// 前序遍历下，root元素后面的一定是左边子树的节点，所以
// preorder.solice(1,rootIndex+1) 获取到左边子树 rootIndex 个元素
// inorder.slice(rootIndex + 1) 是为了过滤掉 根节点
root.left = buildTree(preorder.slice(1, rootIndex + 1), inorder.slice(0, rootIndex));
root.right = buildTree(preorder.slice(rootIndex + 1), inorder.slice(rootIndex + 1));
return root;
};
以上代码首先判断前序遍历的数组是否 1 为空，如果为空直接返回 null。否则，取出前序遍历数组的第一个节点，即根节点的值，然后找到该节点在中序遍历数组中的位置。接着，将中序遍历数组根据该位置分成左子树和右子树两个部分，同时将前序遍历数组根据左子树和右子树的节点数量分成两个部分。递归处理左子树和右子树，并将左右子树的结果作为根节点的左右子节点，最后返回根节点即可。
99. 恢复二叉搜索树
思路分析：
在二叉搜索树中，如果一个节点的值小于左子树中任何一个节点的值，同时又大于右子树中任何一个节点的值，那么这个节点就是正确的。当出现错误的节点时，有且只有两个节点的值是错误的。 我们可以通过中序遍历将所有节点的值存储在一个数组中，然后排序这个数组。接着再次遍历这棵树，将每个错误的节点的值替换为正确的值即可。
Javascript
function recoverTree(root) {
const nodes = [];
const values = [];
inOrder(root, nodes, values);
values.sort((a, b) => a - b);
for (let i = 0; i < nodes.length; i++) {
nodes[i].val = values[i];
}
}
function inOrder(root, nodes, values) {
if (!root) {
return;
}
inOrder(root.left, nodes, values);
nodes.push(root);
values.push(root.val);
inOrder(root.right, nodes, values);
}
时间复杂度：O(n log n) 空间复杂度：O(n) 其中，时间复杂度主要来自于排序算法，空间复杂度则来自于中序遍历存储节点和值的数组。
Javascript
var recoverTree = function (root) {
// 中序 遍历获取到一个有序列表
const nodes = [];
const values = [];
traverse(root);
// 找到 需要交换位置的 2个元素
// 找到 2个元素则为 x,y+1
// 找到一个元素 则为 x,x+1
let x = -1,
y = -1;
for (let i = 0; i < nodes.length - 1; i++) {
if (nodes[i].val > nodes[i + 1].val) {
// 无论是找到 1个点还是2个点，y 都是 i+1
y = i + 1;
if (x == -1) {
x = i;
} else {
// 最多能有2个点，都找到了就退出了
break;
}
}
}
console.log(nodes, x, y);
//交换 nodes 的值，满足有序
let temp = nodes[x].val;
nodes[x].val = nodes[y].val;
nodes[y].val = temp;
function traverse(root) {
if (!root) {
return;
}
traverse(root.left);
nodes.push(root);
traverse(root.right);
}
};
时间复杂度 O(n) 空间复杂度 O(1)
Javascript
const swap = (x, y) => {
const temp = x.val;
x.val = y.val;
y.val = temp;
};
const recoverTree = root => {
let x = null,
y = null,
pred = null;
const traverse = node => {
if (node === null) {
return;
}
traverse(node.left);
if (pred !== null && node.val < pred.val) {
y = node;
if (x === null) {
x = pred;
} else {
return;
}
}
pred = node;
traverse(node.right);
};
traverse(root);
swap(x, y);
};
Morris 遍历 Morris 遍历的核心是建立起来一个临时连接来存储当前节点的前驱。对于一个当前节点，它的前驱是左子树中最右侧的节点。可以将当前节点作为它前驱节点的右子树，这样就可以在遍历时避免使用额外的空间。 Morris 遍历分为两个步骤： 在左子树中找到当前节点的前驱节点。 利用前驱节点建立临时连接，遍历当前节点，然后恢复树的原状。 具体实现步骤如下： 令当前节点为根节点，进行循环。 如果当前节点有左子树，则在左子树中找到当前节点在中序遍历下的前驱节点。具体步骤如下： 找到左子树中最右侧的节点，即当前节点左子树中的最大值。 将前驱节点的右子树指向当前节点，建立临时连接。 将当前节点移动到左子树中。 如果当前节点没有左子树，则输出当前节点的值，然后将当前节点移到右子树中。 重复步骤 1 到步骤 3，直到遍历完整个树。
2347. 最好的扑克手牌
Javascript
/**
* @param {number[]} ranks
* @param {character[]} suits
* @return {string}
*/
var bestHand = function (ranks, suits) {
const suitsSet = new Set(suits);
if (suitsSet.size === 1) {
return 'Flush';
}
const map = new Map();
for (let item of ranks) {
map.set(item, (map.get(item) || 0) + 1);
}
if (map.size === 5) {
return 'High Card';
}
for (const value of map.values()) {
if (value > 2) {
return 'Three of a Kind';
}
}
return 'Pair';
};
94. 二叉树的中序遍历
递归方式
Javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
let ans = [];
traverse(root);
return ans;
function traverse(node) {
if (node == null) return;
traverse(node.left);
ans.push(node.val);
traverse(node.right);
}
};
迭代方式
Javascript
var inorderTraversal = function (root) {
let ans = [];
if (root == null) {
return ans;
}
let stack = [];
let cur = root;
while (cur || stack.length) {
// 先找到第一个子节点，也就是最左边的节点
// 然后再去找 该子节点的右子节点
while (cur) {
stack.push(cur);
cur = cur.left;
}
let last = stack.pop();
ans.push(last.val);
cur = last.right;
}
return ans;
};
95. 不同的二叉搜索树 II
解题思路： 这道题是一道典型的递归问题。我们可以枚举每一个数字 i（i 从 1 到 n）作为当前二叉搜索树的根节点，然后递归构造其左右子树，最后将左右子树的结果合并即可。代码实现可以使用递归函数和回溯的方法。具体步骤如下： 定义递归函数 generateTrees(start, end)，表示构造从 start 到 end 的二叉搜索树。 如果 start > end，则返回 null，表示当前二叉搜索树为空。 定义一个数组 trees 存储当前二叉搜索树的所有可能的根节点。 枚举每一个数字 i（i 从 start 到 end），将 i 作为根节点，递归构造其左右子树。 遍历左右子树的所有可能的组合，并将它们与根节点组合，得到当前二叉搜索树的所有可能情况，并加入 trees 数组中。 返回 trees 数组，表示当前 start 到 end 的所有二叉搜索树的可能情况。
Javascript
var generateTrees = function (n) {
if (n === 0) return [];
return generateTreesDFS(1, n);
};
function generateTreesDFS(start, end) {
if (start > end) return [null];
const trees = [];
for (let i = start; i <= end; i++) {
const leftTrees = generateTreesDFS(start, i - 1);
const rightTrees = generateTreesDFS(i + 1, end);
for (const leftTree of leftTrees) {
for (const rightTree of rightTrees) {
trees.push(new TreeNode(i, leftTree, rightTree));
}
}
}
return trees;
}
98. 验证二叉搜索树
迭代方式遍历二叉树，迭代的同时比较是否有不满足条件的
Javascript
var isValidBST = function (root) {
let stack = [];
let inorder = -Infinity;
while (stack.length || root !== null) {
while (root !== null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
// 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
if (root.val <= inorder) {
return false;
}
inorder = root.val;
root = root.right;
}
return true;
};
递归方式
Javascript
const helper = (root, lower, upper) => {
if (root === null) {
return true;
}
if (root.val <= lower || root.val >= upper) {
return false;
}
return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
};
var isValidBST = function (root) {
return helper(root, -Infinity, Infinity);
};
100. 相同的树
递归
Javascript
var isSameTree = function (p, q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
迭代 迭代可选择 前序遍历，同时遍历 2 颗树
Javascript
function walkPreOrder(root, root2) {
if (root === null && root2 == null) return true;
if (root === null || root2 == null) return false;
const stack = [root];
const stack2 = [root2];
while (stack.length && stack2.length) {
const item = stack.pop();
const item2 = stack2.pop();
// 比较一下
if (item.val !== item2.val) return false;
// 因为后面 子节点 如果是null 的话不会被添加到 stack 里面，所以要提前判断一下，一边为null ，另外一边不为null 的情况
if (item.left == null && item2.left != null) return false;
if (item.left != null && item2.left == null) return false;
if (item.right == null && item2.right != null) return false;
if (item.right != null && item2.right == null) return false;
// Left child is pushed after right one, since we want to print left child first hence it must be above right child in the stack
if (item.right) stack.push(item.right);
if (item.left) stack.push(item.left);
if (item2.right) stack2.push(item2.right);
if (item2.left) stack2.push(item2.left);
}
return stack.length == 0 && stack2.length == 0;
}
101. 对称二叉树
Javascript
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function (root) {
return isSameTree(root, root);
// 判断左边子树 根右边子树是否一致
function isSameTree(left, right) {
if (left == null && right == null) return true;
if (!left || !right) return false;
return left.val == right.val && isSameTree(left.left, right.right) && isSameTree(left.right, right.left);
}
};
102. 二叉树的层序遍历
Javascript BFS
var levelOrder = function (root) {
let ans = [];
if (!root) return ans;
let queue = [root];
while (queue.length) {
let level = [];
let len = queue.length;
for (let i = 0; i < len; ++i) {
const item = queue.shift();
level.push(item.val);
item.left && queue.push(item.left);
item.right && queue.push(item.right);
}
ans.push(level);
}
return ans;
};
103. 二叉树的锯齿形层序遍历
解题思路 层序遍历的过程中，计算 ans 里面是奇数层还是偶数层，奇数层就反转一下数组，或者在每层添加元素的时候选择 unshift
Javascript
var zigzagLevelOrder = function (root) {
let ans = [];
if (!root) return ans;
let queue = [root];
while (queue.length) {
let level = [];
let len = queue.length;
for (let i = 0; i < len; ++i) {
const item = queue.shift();
level.push(item.val);
item.left && queue.push(item.left);
item.right && queue.push(item.right);
}
ans.push(ans.length % 2 == 0 ? level : level.reverse());
}
return ans;
};
104. 二叉树的最大深度
二叉树最大深度 = Math.max(左子树深度，右子树深度)+ 1
Javascript
var maxDepth = function (root) {
if (!root) return 0;
let left = maxDepth(root.left);
let right = maxDepth(root.right);
return Math.max(left, right) + 1;
};
106. 从中序与后序遍历序列构造二叉树
前序遍历 root➝ left ➝ right 后序遍历 left ➝ right ➝ root
解题思路： 中序遍历的第一个节点是左子树的根节点，这样可以确定出根节点在后序遍历中的位置。后序遍历中，根节点的左侧是左子树的节点，右侧是右子树的节点。使用递归的方式，可以构造出整棵树。 具体来说，对于每一次递归调用，先取后序遍历中最后一个节点，确定其为当前树的根节点。然后在中序遍历中找到根节点的位置，位置左侧为左子树，右侧为右子树。此时就可以递归构造左右子树，最后返回当前根节点。
Javascript
var buildTree = function (inorder, postorder) {
if (!inorder.length || !postorder.length) return null;
// 根节点 是后序遍历的最后一个元素
const rootVal = postorder[postorder.length - 1];
const root = new TreeNode(rootVal);
// 可以用hash 表先存一遍，优化一下查找速度
const index = inorder.indexOf(root.val);
// postorder.slice(0,index) 在postorder 中取出左侧不包含根节点的 index 个元素
// postorder.slice(0,len-1) 在postorder 中取出右侧 不包含根节点（最后一个节点）的 所有元素
root.left = buildTree(inorder.slice(0, index), postorder.slice(0, index));
root.right = buildTree(inorder.slice(index + 1), postorder.slice(index, postorder.length - 1));
return root;
};
107. 二叉树的层序遍历 II
解体思路 层序遍历，用队列存储 ans ，每层的结果往队头插入
Javascript
var levelOrderBottom = function (root) {
if (!root) return [];
let queue = [root];
const ans = [];
while (queue.length) {
const len = queue.length;
const level = [];
for (let i = 0; i < len; ++i) {
const item = queue.shift();
level.push(item.val);
item.left && queue.push(item.left);
item.right && queue.push(item.right);
}
ans.unshift(level);
}
return ans;
};
108. 将有序数组转换为二叉搜索树
中加位置的需要用 Math.floor 否则会有死循环
二叉搜索树中序遍历得到的结果是有序数组。有序数组中，中间位置的节点是根节点，因此，每次选择出 中间位置的节点作为根节点，再递归去生成左右 2 边子节点 。
Javascript
var sortedArrayToBST = function (nums) {
const len = nums.length;
if (len == 0) return null;
const rootIndex = Math.floor(len / 2); //or len/2 >> 0
const root = new TreeNode(nums[rootIndex]);
root.left = sortedArrayToBST(nums.slice(0, rootIndex));
root.right = sortedArrayToBST(nums.slice(rootIndex + 1));
return root;
};
109. 有序链表转换二叉搜索树
先遍历一遍 链表得到有序数组（目的是能随机访问 root 节点左右 2 边的节点）
Javascript
var sortedListToBST = function (head) {
// 先遍历一遍，得到有序数组
let values = [];
while (head) {
values.push(head.val);
head = head.next;
}
return buildBST(values);
function buildBST(nums) {
const len = nums.length;
if (len == 0) return null;
const rootIndex = (len / 2) >> 0;
const root = new TreeNode(nums[rootIndex]);
root.left = buildBST(nums.slice(0, rootIndex));
root.right = buildBST(nums.slice(rootIndex + 1));
return root;
}
};
110. 平衡二叉树
解题思路：
自顶向下 递归去 比较左子树，右子树的高度差
Javascript
var isBalanced = function (root) {
if (root == null) return true;
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
// 可优化一下
// if(Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1) {
// return isBalanced(root.left) && isBalanced(root.right);
// }
// return false;
function maxDepth(node) {
if (node == null) return 0;
let left = maxDepth(node.left);
let right = maxDepth(node.right);
return Math.max(left, right) + 1;
}
};
自顶向下存在大量 重复子树的高度计算 时间复杂度： O(n^2) 空间复杂度 O(n)
后序遍历，自底向上，解决重复计算问题。
Javascript
var isBalanced = function (root) {
return depth(root) >= 0;
function depth(node) {
if (node == null) return 0;
let left = depth(node.left);
let right = depth(node.right);
// 后序遍历 当前节点 不满足，或者 左子树，右子树 不满足都 返回 -1
if (Math.abs(left - right) > 1 || left == -1 || right == -1) {
return -1;
}
return Math.max(left, right) + 1;
}
};
111. 二叉树的最小深度
Javascript
var minDepth = function (root) {
if (root == null) return 0;
const left = minDepth(root.left);
const right = minDepth(root.right);
// 需要注意 如果 当前节点中 左子节点 或者右子节点 为空的时候，需要选择其中 最大的那个
// 因为 null 返回的是 0 ，所以可以直接 加起来 left +right +1
return root.left == null || root.right == null ? left + right + 1 : Math.min(left, right) + 1;
};
112. 路径总和
递归的去计算 当前节点所剩的 targetsum 是否等于 root.val 如果相等，并且当前节点是叶子节点则 返回 true
Javascript
var hasPathSum = function (root, targetSum) {
if (root == null) return false;
if (root.val == targetSum && root.left == null && root.right == null) return true;
let left = hasPathSum(root.left, targetSum - root.val);
let right = hasPathSum(root.right, targetSum - root.val);
return left || right;
};
113. 路径总和 II
Javascript
var pathSum = function (root, targetSum) {
let ans = [];
let nodes = [];
helper(root, targetSum);
return ans;
function helper(node, target) {
if (node == null) return;
// 保存路径
nodes.push(node.val);
// 找到一个叶子节点
if (node.left == null && node.right == null && node.val == target) {
ans.push(nodes.slice());
}
helper(node.left, target - node.val);
helper(node.right, target - node.val);
nodes.pop();
}
};
114. 二叉树展开为链表
时间复杂度 O(n) 空间复杂度 O(n)
Javascript
var flatten = function (root) {
let nodes = [];
traverse(root);
const len = nodes.length;
for (let i = 1; i < len; i++) {
let prev = nodes[i - 1],
cur = nodes[i];
prev.left = null;
prev.right = cur;
}
function traverse(node) {
if (node !== null) {
nodes.push(node);
traverse(node.left);
traverse(node.right);
}
}
};
空间复杂度 O(1)
Javascript
var flatten = function (root) {
let cur = root;
while (cur !== null) {
if (cur.left !== null) {
const next = cur.left;
const predecessor = next;
while (predecessor.right !== null) {
predecessor = predecessor.right;
}
// 先序遍历中
// 当前节点左子树最右边的节点 就是 当前节点右节点 的前驱节点
predecessor.right = cur.right;
cur.left = null;
cur.right = next;
}
// 相当于访问链表的 下一个节点
cur = cur.right;
}
};
116. 填充每个节点的下一个右侧节点指针
二叉树层序遍历，需要注意返回值是 Node 类型
Javascript
/**
* @param {Node} root
* @return {Node}
*/
var connect = function (root) {
if (root == null) return root;
let queue = [root];
while (queue.length) {
const len = queue.length;
for (let i = 0; i < len; i++) {
const cur = queue.shift();
// 还有元素，则 next 指向下一个
if (i + 1 < len) {
cur.next = queue[0];
}
cur.left && queue.push(cur.left);
cur.right && queue.push(cur.right);
}
}
return root;
};
进阶： 你只能使用常量级额外空间。 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
Javascript
/**
* @param {Node} root
* @return {Node}
*/
var connect = function (root) {
if (root == null) return root;
let leftMost = root;
// 遍历每一层
while (leftMost.left !== null) {
let head = leftMost;
//每一层中，通过next 指针，用链表的方式去遍历
while (head !== null) {
// 相同父节点，直接连接左右2边节点就行
head.left.next = head.right;
if (head.next) {
head.right.next = head.next.left;
}
// 从左向右 遍历链表
head = head.next;
}
// 切换到下一层开始遍历
leftMost = leftMost.left;
}
return root;
};
[117. 填充每个节点的下一个右侧节点指针 II](117. 填充每个节点的下一个右侧节点指针 II)
创建一个哑节点，用该节点去把 子节点串联起来
Javascript
/**
* @param {Node} root
* @return {Node}
*/
var connect = function (root) {
if (root === null) return root;
let head = root;
while (head !== null) {
let dummyNode = new Node(0);
let prev = dummyNode;
while (head !== null) {
if (head.left !== null) {
prev.next = head.left;
prev = prev.next;
}
if (head.right !== null) {
prev.next = head.right;
prev = prev.next;
}
head = head.next;
}
head = dummyNode.next;
}
return root;
};
129. 求根节点到叶节点数字之和
每个节点都对应一个数字，等于其父节点对应的数字乘以 10 再加上该节点的值（这里假设根节点的父节点对应的数字是 0）。只要计算出每个叶子节点对应的数字，然后计算所有叶子节点对应的数字之和，即可得到结果
Javascript
/**
* @param {TreeNode} root
* @return {number}
*/
var sumNumbers = function (root) {
return dfs(root, 0);
function dfs(node, sum) {
if (node == null) {
return 0;
}
const curSum = sum * 10 + node.val;
if (node.left == null && node.right == null) {
return curSum;
}
return dfs(node.left, curSum) + dfs(node.right, curSum);
}
};
144. 二叉树的前序遍历
递归
Javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function (root) {
let ans = [];
helper(root);
return ans;
function helper(node) {
if (node == null) return;
ans.push(node.val);
helper(node.left);
helper(node.right);
}
};
迭代 迭代过程中需要存储右节点的信息
Javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function (root) {
if (root == null) return [];
let ans = [];
let stack = [root];
while (stack.length) {
const node = stack.pop();
ans.push(node.val);
node.right && stack.push(node.right);
node.left && stack.push(node.left);
}
return ans;
};
145. 二叉树的后序遍历
递归
Javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function (root) {
if (root == null) return [];
let ans = [];
helper(root);
return ans;
function helper(node) {
if (root == null) return;
helper(node.left);
helper(node.right);
ans.push(node.val);
}
};
迭代
先序遍历 root ➝left ➝ right 后序遍历 left ➝ right ➝ root 因此可以把 先序遍历调整一下先遍历右边节点 ，最后把先序遍历的 结果 reverse 一下就行
Javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function (root) {
if (root == null) return [];
let ans = [],
stack = [root];
while (stack.length) {
const item = stack.pop();
ans.push(item.val);
item.left && stack.push(item.left);
item.right && stack.push(item.right);
}
return ans.reverse();
};
94. 二叉树的中序遍历
递归
Javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
let ans = [];
function traverse(node) {
if (node == null) return;
traverse(node.left);
ans.push(node.val);
traverse(node.right);
}
};
迭代
Javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
let ans = [];
if (root == null) {
return ans;
}
let stack = [];
let cur = root;
while (cur || stack.length) {
while (cur) {
stack.push(cur);
cur = cur.left;
}
let last = stack.pop();
ans.push(last.val);
cur = last.right;
}
return ans;
};
156. 上下翻转二叉树
Javascript
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var upsideDownBinaryTree = function (root) {
let right = null,
father = null;
while (root !== null) {
let left = root.left;
root.left = right;
right = root.right;
root.right = father;
father = root;
root = left;
}
return father;
};
173. 二叉搜索树迭代器
核心代码是 generator 函数 用迭代方式实现 中序遍历
Javascript
/**
* @param {TreeNode} root
*/
var BSTIterator = function (root) {
this.nodes = inorderTraversal(root);
this.prev = this.nodes.next();
};
/**
* @return {number}
*/
BSTIterator.prototype.next = function () {
let res = this.prev.value;
this.prev = this.nodes.next();
return res;
};
/**
* @return {boolean}
*/
BSTIterator.prototype.hasNext = function () {
return !this.prev.done;
};
function* inorderTraversal(root) {
if (root == null) return null;
let cur = root,
stack = [];
while (cur !== null || stack.length) {
// 找到 leftMost 节点
while (cur !== null) {
stack.push(cur);
cur = cur.left;
}
const item = stack.pop();
yield item.val;
cur = item.right;
}
}
next 方法执行的时候去中序遍历
Javascript
var BSTIterator = function (root) {
this.cur = root;
this.stack = [];
};
BSTIterator.prototype.next = function () {
// 中序遍历
while (this.cur) {
this.stack.push(this.cur);
this.cur = this.cur.left;
}
this.cur = this.stack.pop();
const ret = this.cur.val;
this.cur = this.cur.right;
return ret;
};
BSTIterator.prototype.hasNext = function () {
return this.cur !== null || this.stack.length;
};
199. 二叉树的右视图
层序遍历 先遍历右边节点，方便通过 queue[0] 获取到节点
Javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function (root) {
if (root === null) return [];
let ans = [];
let queue = [root];
while (queue.length) {
const len = queue.length;
ans.push(queue[0].val);
for (let i = 0; i < len; i++) {
const item = queue.shift();
item.right && queue.push(item.right);
item.left && queue.push(item.left);
}
}
return ans;
};
222. 完全二叉树的节点个数
节点个数等于每个节点加上左右子节点 的累积值
Javascript
/**
* @param {TreeNode} root
* @return {number}
*/
var countNodes = function (root) {
if (root == null) return 0;
return helper(root);
function helper(node) {
if (node == null) return 0;
return helper(node.left) + helper(node.right) + 1;
}
};
226. 翻转二叉树
Javascript
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function (root) {
if (root == null) return null;
let left = root.left;
root.left = root.right;
root.right = left;
invertTree(root.left);
invertTree(root.right);
return root;
};
230. 二叉搜索树中第 K 小的元素
方法一：中序遍历
二叉搜索树，中序遍历获取到有序数组，在通过索引随机访问
Javascript
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function (root, k) {
let values = [];
traveres(root);
return values[k - 1];
function traveres(root) {
if (root === null) return;
traveres(root.left);
values.push(root.val);
traveres(root.right);
}
};
改进一下，遍历到第 k 个就结束。通过 count 计算目前遍历到第几个值，无需 stack 存储所有遍历过的值
Javascript
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function (root, k) {
let count = 0;
let ans = -1;
traverse(root);
return ans;
function traverse(root) {
if (root === null) return;
traverse(root.left);
count++;
if (count === k) {
ans = root.val;
return;
}
traverse(root.right);
}
};
方法二：进阶
平衡二叉树
671. 二叉树中第二小的节点
Javascript
/**
* @param {TreeNode} root
* @return {number}
*/
var findSecondMinimumValue = function (root) {
let ans = -1;
let min = root.val;
helper(root);
return ans;
function helper(root) {
if (root === null) return;
// 节点处的值是最小值，如果 >= 已经找到的，说明没有更小的了，
if (ans !== -1 && root.val >= ans) {
return;
}
if (root.val > min) {
ans = root.val;
}
helper(root.left);
helper(root.right);
}
};
235. 二叉搜索树的最近公共祖先
注意二叉搜索树特性
前序遍历，递归查找符合以下条件的节点 当前节点的值 val 符合 min < val < max
当前节点等于其中任何一个节点
Javascript
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
if (root === null) return;
let min = Math.min(p.val, q.val);
let max = Math.max(p.val, q.val);
let ans = null;
helper(root, min, max);
return ans;
function helper(root, min, max) {
if (root === null) return;
// 左右2边个一个节点的情况
if (root.val > min && root.val < max) {
ans = root;
return;
}
// 有一个节点等于当前节点的
if (root.val === min || root.val === max) {
ans = root;
return;
}
helper(root.left, min, max);
helper(root.right, min, max);
}
};
236. 二叉树的最近公共祖先
自底向上递归遍历
Javascript
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
if (root == null) return;
let ans = null;
helper(root, p, q);
return ans;
function helper(root, p, q) {
if (root == null) return false;
let left = helper(root.left, p, q);
let right = helper(root.right, p, q);
// 第一种情况，该节点左右2边都是
if (left && right) {
ans = root;
}
const isRoot = root.val === p.val || root.val === q.val;
// 第2种情况，左边或者右边 有一个，root 是其中一个
if (isRoot && (left || right)) {
ans = root;
}
return left || right || isRoot;
}
};
250. 统计同值子树
递归计算每个节点是否满足以下条件 没有左右子节点 有左右子节点，左右子树都是同值子树，并且等于 root.val 有左子节点，左子节点是同值子树，并且等于 root.val 有右子节点，右子节点是同值子树，并且等于 root.val
Javascript
/**
* @param {TreeNode} root
* @return {number}
*/
var countUnivalSubtrees = function (root) {
if (root == null) return 0;
let count = 0;
traverse(root);
return count;
function traverse(root) {
if (root === null) return true;
if (root.left === null && root.right == null) {
count++;
return true;
}
let isUnival = true;
if (root.left !== null && root.right !== null) {
let left = traverse(root.left) && root.left.val == root.val;
let right = traverse(root.right) && root.right.val == root.val;
isUnival = left && right;
} else if (root.left !== null) {
let left = traverse(root.left) && root.left.val == root.val;
isUnival = left;
} else if (root.right !== null) {
let right = traverse(root.right) && root.right.val == root.val;
isUnival = right;
}
if (!isUnival) return false;
count++;
return true;
}
};
255. 验证前序遍历序列二叉搜索树
单调栈
Javascript
/**
* @param {number[]} preorder
* @return {boolean}
*/
var verifyPreorder = function (preorder) {
const stack = [];
let min = 0;
for (const val of preorder) {
console.log(stack);
// 出栈的时候 存一下最小值，比较一下
if (val < min) {
return false;
}
while (stack.length && val > stack[stack.length - 1]) {
min = stack.pop();
}
stack.push(val);
}
// console.log(stack);
return true;
};
257. 二叉树的所有路径
时间复杂度： O(N ^2 ) 空间复杂度： O(N ^2 )
递归
Javascript
/**
* @param {TreeNode} root
* @return {string[]}
*/
var binaryTreePaths = function (root) {
let ans = [];
traverse(root, '');
return ans;
function traverse(root, path) {
if (root === null) return;
path += root.val.toString();
if (root.left === null && root.right === null) {
ans.push(path);
} else {
path += '->';
traverse(root.left, path);
traverse(root.right, path);
}
}
};
270. 最接近的二叉搜索树值
时间复杂度：O(H) 空间复杂度：O(1)
Javascript
/**
* @param {TreeNode} root
* @param {number} target
* @return {number}
*/
var closestValue = function (root, target) {
let distance = Number.MAX_VALUE;
let ans = -1;
helper(root, target);
return ans;
function helper(root, target) {
if (root === null) return;
let newDis = Math.abs(target - root.val);
if (newDis < distance) {
distance = newDis;
ans = root.val;
}
if (target > root.val) {
helper(root.right, target);
} else {
helper(root.left, target);
}
}
};
272. 最接近的二叉搜索树值 II
方法一 先中序遍历，得到一个有序队列，顺便找出其中最接近 target 的 索引 minIndex ,再通过 2 个指针，从最小距离索引出开始像左右 2 边遍历得到 K 个值
Javascript
/**
* @param {TreeNode} root
* @param {number} target
* @param {number} k
* @return {number[]}
*/
var closestKValues = function (root, target, k) {
let values = [],
distance = Number.MAX_VALUE,
minIndex = -1,
ans = [];
traverse(root);
const len = values.length;
ans.push(values[minIndex]);
let i = minIndex - 1,
j = minIndex + 1;
while (ans.length < k) {
if (i < 0) {
ans.push(values[j++]);
} else if (j >= len) {
ans.push(values[i--]);
} else if (Math.abs(values[i] - target) > Math.abs(values[j] - target)) {
ans.push(values[j++]);
} else {
ans.push(values[i--]);
}
}
return ans;
function traverse(root) {
if (root === null) return;
traverse(root.left);
values.push(root.val);
let curDis = Math.abs(root.val - target);
if (curDis < distance) {
distance = curDis;
minIndex = values.length - 1;
}
traverse(root.right);
}
};
方法二 迭代方式实现中序遍历
无需遍历完所有值，虽然时间复杂度整体还是 O(n) ，但是平均时间复杂度小于 O(n)
Javascript
var closestKValues = function (root, target, k) {
let values = [],
stack = [],
ans = [];
// 迭代方式中序遍历
let cur = root;
while (stack.length || cur) {
while (cur !== null) {
stack.push(cur);
cur = cur.left;
}
const item = stack.pop();
let curDis = Math.abs(item.val - target);
while (values.length !== 0 && curDis > Math.abs(values[values.length - 1] - target)) {
const smallest = values.pop();
ans.push(smallest);
// 提前退出递归
if (ans.length === k) {
return ans;
}
}
values.push(item.val);
cur = item.right;
}
if (ans.length < k) {
ans = ans.concat(values.slice([ans.length - k]));
}
return ans;
};
285. 二叉搜索树中的中序后继
时间复杂度 O(n) 空间复杂度 O(n)
方法一
递归实现中序遍历，遍历到 当前节点的上一个节点 等于 P 的时候结束
Javascript
var inorderSuccessor = function (root, p) {
let prev = null;
let ans = null;
helper(root);
return ans;
function helper(root) {
if (root === null || ans !== null) return null;
helper(root.left);
if (prev !== null && prev.val === p.val) {
ans = root;
}
prev = root;
helper(root.right);
}
};
迭代
Javascript
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @return {TreeNode}
*/
var inorderSuccessor = function (root, p) {
let stack = [];
let prev = null;
let cur = root;
while (cur !== null || stack.length) {
while (cur !== null) {
stack.push(cur);
cur = cur.left;
}
const item = stack.pop();
console.log(stack);
if (prev !== null && prev.val === p.val) {
return item;
}
prev = item;
cur = item.right;
}
return null;
};
方法二
时间复杂度 O(n) 空间复杂度 O(1)
Javascript
var inorderSuccessor = function (root, p) {
let successor = null;
if (p.right) {
successor = p.right;
while (successor.left) {
successor = successor.left;
}
return successor;
}
let node = root;
while (node) {
if (node.val > p.val) {
successor = node;
node = node.left;
} else {
node = node.right;
}
}
return successor;
};
297. 二叉树的序列化与反序列化
Javascript
var serialize = function (root) {
return rserialize(root, '');
};
var deserialize = function (data) {
const dataArray = data.split(',');
return rdeserialize(dataArray);
};
const rserialize = (root, str) => {
if (root === null) {
str += 'None,';
} else {
str += root.val + '' + ',';
str = rserialize(root.left, str);
str = rserialize(root.right, str);
}
return str;
};
const rdeserialize = dataList => {
if (dataList[0] === 'None') {
dataList.shift();
return null;
}
const root = new TreeNode(parseInt(dataList[0]));
dataList.shift();
root.left = rdeserialize(dataList);
root.right = rdeserialize(dataList);
return root;
};
298. 二叉树最长连续序列
Javascript
var longestConsecutive = function (root) {
let ans = 0;
helper(root, null, 0);
return ans;
function helper(root, parent, len) {
if (root === null) return;
len = parent !== null && parent.val + 1 === root.val ? len + 1 : 1;
ans = Math.max(ans, len);
helper(root.left, root, len);
helper(root.right, root, len);
}
};
314. 二叉树的垂直遍历
前序遍历不能保证 节点是从上往下排列，所以需要层序遍历,自顶向下，从左到右遍历 根元素默认为 0 ，左边= root -1, 右边 = root +1
Javascript
var verticalOrder = function (root) {
if (root === null) return [];
let ans = [],
queue = [[root, 0]],
minLeft = 0,
map = new Map();
while (queue.length) {
const [item, index] = queue.shift();
// 更新一下最小 的index
minLeft = Math.min(minLeft, index);
let prevVal = map.get(index);
map.set(index, prevVal ? prevVal.concat(item.val) : [item.val]);
item.left && queue.push([item.left, index - 1]);
item.right && queue.push([item.right, index + 1]);
}
for (const key of map.keys()) {
// 加上最小的index 即可转变为所有索引从 0 到 n
ans[-minLeft + key] = map.get(key);
}
return ans;
};
331. 验证二叉树的前序序列化
方法一
计算出入度 剩余槽位
Javascript
var isValidSerialization = function (preorder) {
const nodes = preorder.split(',');
let diff = 1;
for (let val of nodes) {
diff -= 1;
if (diff < 0) {
return false;
}
if (val !== '#') {
diff += 2;
}
}
return diff === 0;
};
333. 最大 BST 子树
方法一：
时间复杂度 O(n^2)
Javascript
var largestBSTSubtree = function (root) {
const valid = function (node, min, max) {
if (node === null) return true;
if (node.val <= min || node.val >= max) return false;
return valid(node.left, min, node.val) && valid(node.right, node.val, max);
};
const cnt = function (node) {
if (node === null) return 0;
return cnt(node.left) + cnt(node.right) + 1;
};
if (root === null) return 0;
if (valid(root, -Infinity, Infinity)) return cnt(root);
return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
};
方法二
时间复杂度 O(n)
Javascript
var largestBSTSubtree = function (root) {
let ans = 0;
const dfs = function (root) {
if (!root) {
return [true, Infinity, -Infinity, 0];
}
const [leftIsBST, leftMin, leftMax, leftCount] = dfs(root.left);
const [rightIsBST, rightMin, rightMax, rightCount] = dfs(root.right);
const isBST = leftIsBST && rightIsBST && root.val > leftMax && root.val < rightMin;
const min = isBST ? Math.min(leftMin, root.val) : -Infinity;
const max = isBST ? Math.max(rightMax, root.val) : Infinity;
const count = isBST ? leftCount + rightCount + 1 : 0;
ans = Math.max(ans, count);
return [isBST, min, max, count];
};
dfs(root);
return ans;
};
366. 寻找二叉树的叶子节点
后序遍历，自底向上，求解每个节点的高度，高度一致的存储到一起
Javascript
var findLeaves = function (root) {
let ans = [];
helper(root);
return ans;
function helper(root) {
if (root === null) return 0;
let left = helper(root.left);
let right = helper(root.right);
let depth = Math.max(left, right) + 1;
if (!ans[depth - 1]) {
ans[depth - 1] = [];
}
// 第一层 从 0 开始
ans[depth - 1].push(root.val);
return depth;
}
};
404. 左叶子之和
Javascript
var sumOfLeftLeaves = function (root) {
return dfs(root);
function dfs(root) {
let ans = 0;
if (root === null) return 0;
if (root.left !== null) {
ans += isLeaf(root.left) ? root.left.val : dfs(root.left);
}
if (root.right !== null && !isLeaf(root.right)) {
ans += dfs(root.right);
}
return ans;
}
function isLeaf(root) {
return root.left === null && root.right === null;
}
};
426. 将二叉搜索树转化为排序的双向链表
中序遍历
Javascript
var treeToDoublyList = function (root) {
if (root === null) return null;
let head = null,
last = null;
dfs(root);
// 首尾
head.left = last;
last.right = head;
return head;
function dfs(root) {
if (root === null) return null;
dfs(root.left);
if (head === null) {
head = root;
}
if (last !== null) {
last.right = root;
root.left = last;
}
last = root;
dfs(root.right);
}
};
431. 将 N 叉树编码为二叉树
Javascript
/**
* // Definition for a Node.
* function Node(val, children) {
* this.val = val;
* this.children = children;
* };
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
class Codec {
constructor() {}
/**
* @param {Node|null} root
* @return {TreeNode|null}
*/
// Encodes an n-ary tree to a binary tree.
encode = function (root) {
if (root === null) return null;
let node = new TreeNode(root.val);
if (root.children.length === 0) return node;
let leftNode = this.encode(root.children[0]);
node.left = leftNode;
const len = root.children.length;
for (let i = 1; i < len; i++) {
leftNode.right = this.encode(root.children[i]);
leftNode = leftNode.right;
}
return node;
};
/**
* @param {TreeNode|null} root
* @return {Node|null}
*/
// Decodes your binary tree to an n-ary tree.
decode = function (root) {
if (root === null) return null;
let node = new Node(root.val, []);
if (root.left === null) return node;
let child = root.left;
while (child !== null) {
node.children.push(this.decode(child));
child = child.right;
}
return node;
};
}
/*
* Your Codec object will be instantiated and called as such:
* codec = Codec()
* codec.decode(codec.encode(root))
*/
515. 在每个树行中找最大值
剑指 Offer II 044. 二叉树每层的最大值
广度优先，层序遍历
Javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var largestValues = function (root) {
if (root === null) return [];
let ans = [];
let queue = [root];
while (queue.length) {
const len = queue.length;
let max = -Infinity;
for (let i = 0; i < len; i++) {
const item = queue.shift();
max = Math.max(item.val, max);
item.left && queue.push(item.left);
item.right && queue.push(item.right);
}
ans.push(max);
}
return ans;
};
深度优先 通过节点高度来判断是否在同一层。通过递归函数参数保留 节点的高度
Javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var largestValues = function (root) {
if (root === null) return [];
let ans = [];
dfs(root, 0);
return ans;
function dfs(root, level) {
// 每层第一个元素
if (level === ans.length) {
ans.push(root.val);
} else {
// 比较一下大小，把最大的填进去
ans.splice(level, 1, Math.max(ans[level], root.val));
}
root.left && dfs(root.left, level + 1);
root.right && dfs(root.right, level + 1);
}
};
面试题 04.02. 最小高度树
选择出根节点，递归去创建左右子节点
Javascript
function sortedArrayToBST(nums) {
if (!nums.length) return null;
const mid = Math.floor(nums.length / 2);
const root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid + 1));
return root;
}