【LeetCode与《代码随想录》】二叉树篇：做题笔记与总结-JavaScript版

代码随想录

代码随想录
代码随想录CSDN官方

前、中、后指的都是根的位置。

144. 二叉树的前序遍历

https://leetcode.cn/problems/binary-tree-preorder-traversal/

var preorderTraversal = function (root) {// 前序遍历：中 左 右let ans = []const dfs = function (root) {if (root === null) return;ans.push(root.val);dfs(root.left);dfs(root.right);}dfs(root);return ans;
};

94. 二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/

var inorderTraversal = function (root) {let ans = []const dfs = function (root) {if (root === null) return;// 中序:左中右dfs(root.left);ans.push(root.val);dfs(root.right);}dfs(root);return ans;
};

145. 二叉树的后序遍历

https://leetcode.cn/problems/binary-tree-postorder-traversal/

var postorderTraversal = function (root) {let ans = []const dfs = function (root) {if (root === null) return;// 后序:左右中dfs(root.left);dfs(root.right);ans.push(root.val);}dfs(root);return ans;
};

102.二叉树的层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/

var levelOrder = function (root) {let ans = [], queue = []if (root === null) return ans;queue.push(root);while (queue.length) {let len = queue.length;let anss = [];for (let i = 0; i < len; i++) {let node = queue.shift();anss.push(node.val);node.left && queue.push(node.left);node.right && queue.push(node.right);}ans.push(anss);}return ans;
};

226.翻转二叉树

https://leetcode.cn/problems/invert-binary-tree/

var invertTree = function (root) {const dfs = function (root) {if (root === null) return;dfs(root.left);dfs(root.right);[root.left, root.right] = [root.right, root.left];}dfs(root);return root;
};

101. 对称二叉树

https://leetcode.cn/problems/symmetric-tree/

var isSymmetric = function (root) {let ans = true;if (root === null) return ans;if (root.left && root.right === null) return false;if (root.right && root.left === null) return false;const dfs = function (l, r) {if (!l && !r) return;if (l && !r) {ans = false; return;}if (!l && r) {ans = false; return;}if (l.val !== r.val) {ans = false;return;}dfs(l.left, r.right);dfs(l.right, r.left);}dfs(root.left, root.right);return ans;
};

104.二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/

var maxDepth = function (root) {let ans = 0;if (!root) return ans;let q = [];q.push(root);while (q.length) {ans++;let len = q.length;for (let i = 0; i < len; i++) {let node = q.shift();node.left && q.push(node.left);node.right && q.push(node.right);}}return ans;
};

111.二叉树的最小深度

https://leetcode.cn/problems/minimum-depth-of-binary-tree/

var minDepth = function (root) {// 若一个节点没有叶子节点，则结束let ans = 0;if (!root) return ans;let q = [];q.push(root);while (q.length) {ans++;let len = q.length;for (let i = 0; i < len; i++) {let node = q.shift();if (!node.left && !node.right) return ans;node.left && q.push(node.left);node.right && q.push(node.right);}}
};

222.完全二叉树的节点个数

https://leetcode.cn/problems/count-complete-tree-nodes/

注意：要利用完全二叉树的性质。

var countNodes = function (root) {if (!root) return 0;let l = root.left, r = root.right;let ll = 0, rr = 0;while (l) {ll++; l = l.left;}while (r) {rr++; r = r.right;}if (ll === rr) {return Math.pow(2, ll + 1) - 1;}else {return countNodes(root.left) + countNodes(root.right) + 1;}
};

110.平衡二叉树

https://leetcode.cn/problems/balanced-binary-tree/

var isBalanced = function (root) {var getHeight = function (root) {if (!root) return 0;let l = getHeight(root.left);if (l === -1) return -1;let r = getHeight(root.right);if (r === -1) return -1;if (Math.abs(l - r) > 1) return -1;else return Math.max(l, r) + 1;}let ans = getHeight(root);if (ans === -1) return false;else return true;
};

257. 二叉树的所有路径

https://leetcode.cn/problems/binary-tree-paths/

var binaryTreePaths = function (root) {let ans = [], anss = [];var dfs = function (root) {anss.push(root.val);root.left && dfs(root.left);root.right && dfs(root.right);if (!root.left && !root.right) {ans.push(anss.join('->'));}anss.pop();}dfs(root);return ans;
};

404.左叶子之和

https://leetcode.cn/problems/sum-of-left-leaves/

var sumOfLeftLeaves = function (root) {let ans = 0;var dfs = function (root, flag) {if (!root) return;root.left && dfs(root.left, 1);root.right && dfs(root.right, 0);if (flag === 1 && !root.left && !root.right) {ans += root.val;}}dfs(root);return ans;
};

513.找树左下角的值

https://leetcode.cn/problems/find-bottom-left-tree-value/

var findBottomLeftValue = function (root) {// 记录bfs每一层的第一个let ans = root.val, q = [];q.push(root);while (q.length) {let len = q.length;for (let i = 0; i < len; i++) {let node = q.shift();if (!i) ans = node.val;node.left && q.push(node.left);node.right && q.push(node.right);}}return ans;
};

112. 路径总和

https://leetcode.cn/problems/path-sum/

var hasPathSum = function (root, targetSum) {let ans = 0, flag = false;var dfs = function (root) {if (root.left) {ans += root.left.val;dfs(root.left);ans -= root.left.val;}if (root.right) {ans += root.right.val;dfs(root.right);ans -= root.right.val;}if (!root.left && !root.right) {if (ans === targetSum) flag = true;}}if (root) {ans += root.val;dfs(root);}return flag;
};

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

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

var buildTree = function (inorder, postorder) {if (!inorder.length) return null;let rootVal = postorder.pop();let rootIndex = inorder.indexOf(rootVal);let node = new TreeNode(rootVal);node.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex));node.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex));return node;
};

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

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

var buildTree = function (preorder, inorder) {if (!preorder.length) return null;let rootVal = preorder.shift();let rootIndex = inorder.indexOf(rootVal);let node = new TreeNode(rootVal);node.left = buildTree(preorder.slice(0, rootIndex), inorder.slice(0, rootIndex));node.right = buildTree(preorder.slice(rootIndex), inorder.slice(rootIndex + 1));return node;
};

654.最大二叉树

https://leetcode.cn/problems/maximum-binary-tree/

var constructMaximumBinaryTree = function (nums) {// 数组的左右边界var dfs = function (l, r) {if (l > r) return null;let maxVal = -1, maxIndex = -1;for (let i = l; i <= r; i++) {if (nums[i] > maxVal) {maxVal = nums[i];maxIndex = i;}}const node = new TreeNode(maxVal);node.left = dfs(l, maxIndex - 1);node.right = dfs(maxIndex + 1, r);return node;}return dfs(0, nums.length - 1);
};

617.合并二叉树

https://leetcode.cn/problems/merge-two-binary-trees/

var mergeTrees = function (root1, root2) {// 参数:对应相同位置的两个节点var dfs = function (n1, n2) {if (!n1 && !n2) return null;if (n1 && !n2) return n1;if (n2 && !n1) return n2;let node = new TreeNode(n1.val + n2.val);node.left = dfs(n1.left, n2.left);node.right = dfs(n1.right, n2.right);return node;}return dfs(root1, root2);
};

700.二叉搜索树中的搜索

https://leetcode.cn/problems/search-in-a-binary-search-tree/

注意：要利用二叉搜索树的性质。

var searchBST = function (root, val) {let ans = null;var find = function (root) {if (root) {if (root.val === val) {ans = root;return;}if (val < root.val) find(root.left);if (val > root.val) find(root.right);}}find(root);return ans;
};

98.验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/

注意：要判断每一个子树是否是二叉搜索树。

要用到二叉搜索树的性质：其中序遍历是一个递增的序列。

var isValidBST = function (root) {let arr = [];var dfs = function (root) {if (root) {dfs(root.left);arr.push(root.val);dfs(root.right);}}dfs(root);let ans = true;for (let i = 1; i < arr.length; i++) {if (arr[i] <= arr[i - 1]) {ans = false;break;}}return ans;
};

530.二叉搜索树的最小绝对差

https://leetcode.cn/problems/minimum-absolute-difference-in-bst/

var getMinimumDifference = function (root) {let arr = [];var dfs = function (root) {if (root) {dfs(root.left);arr.push(root.val);dfs(root.right);}}let ans = 100000 + 1;dfs(root);for (let i = 1; i < arr.length; i++) {let temp = Math.abs(arr[i] - arr[i - 1]);ans = Math.min(ans, temp);}return ans;
};

501.二叉搜索树中的众数

https://leetcode.cn/problems/find-mode-in-binary-search-tree/

用了额外的空间：

var findMode = function (root) {let arr = []var dfs = function (root) {if (root) {arr.push(root.val);root.left && dfs(root.left);root.right && dfs(root.right);}}dfs(root);let ans = new Map();for (let i = 0; i < arr.length; i++) {ans.set(arr[i], (ans.get(arr[i]) || 0) + 1);}let anss = Array.from(ans);anss.sort((a, b) => (b[1] - a[1]));// console.log(anss)let res = [], num = anss[0][1];for (let i = 0; i < anss.length; i++) {if (anss[i][1] === num) {res.push(anss[i][0]);}else {break;}}return res;
};

没有用额外的空间：

var findMode = function (root) {let ans = [], maxx = 0, nowVal = 100000 + 1, nowNum = 0;var dfs = function (root) {if (root) {root.left && dfs(root.left);if (nowVal === root.val) {nowNum++;}else {nowNum = 1;nowVal = root.val;}if (nowNum === maxx) {ans.push(root.val);}else if (nowNum > maxx) {ans = [];maxx = nowNum;ans.push(root.val);}root.right && dfs(root.right);}}dfs(root);return ans;
};

两项的差距还是比较大的，建议练习“不用额外空间”的版本。

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

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

要找公共祖先，显然要从下往上找，即后序遍历。

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

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

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

• 要用二叉搜索树的性质：根节点与子树的大小关系
• 从根往下遍历，若根节点的值大于pq的值，则往左子树遍历，反之亦然
• 当第一次出现根的值在pq之间时，这就是最近的公共祖先
• 原因：
• 当出现根的值在pq之间时，说明pq一个在根的左子树，一个在根的右子树，若往左遍历会错过右子树的目标，若往右遍历会错过左子树的目标
• 有没有可能此时的根不是最近的祖先节点，而是次近的？答：绝无可能。在数值上是不符合搜索二叉树的性质的。次近的祖先节点不会在pq的值之间，只会比max(p,q)大，或比min(p,q)小

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

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

https://leetcode.cn/problems/insert-into-a-binary-search-tree/

var insertIntoBST = function (root, val) {let ans = false;if (root === null) {root = new TreeNode(val);return root;}var dfs = function (root) {if (root && !ans) {if (val > root.val) {// 往右if (root.right) dfs(root.right);else {root.right = new TreeNode(val);ans = true;return;}}else if (val < root.val) {// 往左if (root.left) dfs(root.left);else {root.left = new TreeNode(val)ans = true;return;}}}}dfs(root);return root;
};

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

https://leetcode.cn/problems/delete-node-in-a-bst/

注意：分类讨论。

• 要删除的key不存在
• 要删除的key：
• 是叶子节点（无左无右）
• 不是叶子节点但只有一个子树
• 不是叶子节点但有两个子树

注意根节点是key的情况。

var deleteNode = function (root, key) {// flag 1左节点删 2右节点删let find = false, parent = null, flag = 0;// 删除key节点var deletee = function (root, flag) {let node = null;if (flag === 1) {node = root.left;} else if (flag === 2) {node = root.right;}// 要删除节点为叶子节点if (!node.left && !node.right) {if (flag === 1) {root.left = null;} else if (flag === 2) {root.right = null;}return;}// 要删除的节点只有一个子节点else if (node.left && !node.right) {if (flag === 1) {root.left = node.left;} else if (flag === 2) {root.right = node.left;}return;}else if (node.right && !node.left) {if (flag === 1) {root.left = node.right;} else if (flag === 2) {root.right = node.right;}return;}// 要删除的节点有两个子节点else if (node.left && node.right) {// 右边接到左边let num = node.right.val, ans = false;var solve = function (roott) {if (roott && !ans) {if (num > roott.val) {if (roott.right) solve(roott.right);else {roott.right = node.right;ans = true; return;}}else if (num < roott.val) {if (roott.left) solve(roott.left);else {roott.left = node.right;ans = true; return;}}}}solve(node.left);if (flag === 1) {root.left = node.left;} else if (flag === 2) {root.right = node.left;}}}// 查找key节点是否存在var findKey = function (root) {if (root && !find) {if (root.left && root.left.val === key) {find = true;parent = root;flag = 1;return;}if (root.right && root.right.val === key) {find = true;parent = root;flag = 2;return;}findKey(root.left);findKey(root.right);}}// 根节点单独计算if (root && root.val === key) {// 左右子树都不为空if (root.left && root.right) {let ans = false, val = root.right.val;var dfs = function (node) {if (node && !ans) {if (val > node.val) {if (node.right) dfs(node.right);else {node.right = root.right;ans = true; return;}}if (val < node.val) {if (node.left) dfs(node.left);else {node.left = root.right;ans = true; return;}}}}dfs(root.left);return root.left;} else if (root.left) {return root.left;} else if (root.right) {return root.right;} else {return null;}}// 没找到findKey(root);if (find === false) return root;// 找到了deletee(parent, flag);return root;
};

上面代码写的乱七八糟的（像是半递归半模拟），下面是可读性更高的代码，来自《代码随想录》

其实就是用好递归。

var deleteNode = function (root, key) {if (!root) return null;if (root.val < key) {root.right = deleteNode(root.right, key);return root;}else if (root.val > key) {root.left = deleteNode(root.left, key);return root;} else {// 找到要删除的节点if (!root.left && !root.right) return null;else if (root.left && !root.right) return root.left;else if (root.right && !root.left) return root.right;else {// 左右节点都在let rightNode = root.right;let minNodee = minNode(rightNode);root.val = minNodee.val;root.right = deleteNode(root.right, minNodee.val);return root;}}
};var minNode = function (root) {while (root.left) {root = root.left;}return root;
}

669. 修剪二叉搜索树

https://leetcode.cn/problems/trim-a-binary-search-tree/

题解

var trimBST = function (root, low, high) {if (root === null) return null;if (root.val > high) return trimBST(root.left, low, high);if (root.val < low) return trimBST(root.right, low, high);root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;
};

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

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

var sortedArrayToBST = function (nums) {var dfs = function (l, r) {if (l > r) return null;let mid = Math.floor(l + (r - l) / 2);let root = new TreeNode(nums[mid]);root.left = dfs(l, mid - 1);root.right = dfs(mid + 1, r);return root;}return dfs(0, nums.length - 1);
};

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

https://leetcode.cn/problems/convert-bst-to-greater-tree/

把二叉搜索树转为数组，数组累加后再赋值给二叉树。

var convertBST = function (root) {if (root === null) return null;let arr = [];var getNum = function (root) {if (root) {getNum(root.left);arr.push(root.val);getNum(root.right);}}getNum(root);for (let i = arr.length - 2; i >= 0; i--) {arr[i] += arr[i + 1];}var solve = function (root) {if (root) {solve(root.left);root.val = arr[i++];solve(root.right);return root;}}let i = 0;return solve(root);
};

更简洁的方法：累加的顺序是右中左，按照此顺序递归累加即可。

var convertBST = function (root) {// 右中左if (!root) return null;let ans = 0;var dfs = function (root) {if (root) {dfs(root.right);ans += root.val;root.val = ans;dfs(root.left);return root;}}return dfs(root);
};

相关题目

107.二叉树的层次遍历II

https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/

var levelOrderBottom = function (root) {let ans = [], queue = []if (root === null) return [];queue.push(root);while (queue.length) {let len = queue.length;let anss = []for (let i = 0; i < len; i++) {let node = queue.shift();anss.push(node.val);node.left && queue.push(node.left);node.right && queue.push(node.right);}ans.unshift(anss);}return ans;
};

199.二叉树的右视图

https://leetcode.cn/problems/binary-tree-right-side-view/

var rightSideView = function (root) {// 每一层的最后一个let ans = [], queue = [];if (root === null) return [];queue.push(root);while (queue.length) {let len = queue.length;for (let i = 0; i < len; i++) {let node = queue.shift();node.left && queue.push(node.left);node.right && queue.push(node.right);if (i === len - 1) {ans.push(node.val);}}}return ans;
};