阿里云 wordpress搭建网站,外贸企业网站对外贸的重要性,网站开发软件标书范本,微商引流被加方法精准客源文章目录代码随想录144. 二叉树的前序遍历94. 二叉树的中序遍历145. 二叉树的后序遍历102.二叉树的层序遍历226.翻转二叉树101. 对称二叉树104.二叉树的最大深度111.二叉树的最小深度222.完全二叉树的节点个数110.平衡二叉树257. 二叉树的所有路径404.左叶子之和513.找树左下角…
文章目录代码随想录144. 二叉树的前序遍历94. 二叉树的中序遍历145. 二叉树的后序遍历102.二叉树的层序遍历226.翻转二叉树101. 对称二叉树104.二叉树的最大深度111.二叉树的最小深度222.完全二叉树的节点个数110.平衡二叉树257. 二叉树的所有路径404.左叶子之和513.找树左下角的值112. 路径总和106.从中序与后序遍历序列构造二叉树105. 从前序与中序遍历序列构造二叉树654.最大二叉树617.合并二叉树700.二叉搜索树中的搜索98.验证二叉搜索树530.二叉搜索树的最小绝对差501.二叉搜索树中的众数236. 二叉树的最近公共祖先235. 二叉搜索树的最近公共祖先701.二叉搜索树中的插入操作450.删除二叉搜索树中的节点669. 修剪二叉搜索树108.将有序数组转换为二叉搜索树538.把二叉搜索树转换为累加树相关题目107.二叉树的层次遍历II199.二叉树的右视图代码随想录
代码随想录 代码随想录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;
};
