叉树
- 二叉树的遍历
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
- 二叉树的属性
- 对称二叉树
- 二叉树最大深度
- 二叉树最小深度
- 完全二叉树的节点个数
- 平衡二叉树
- 二叉树的所有路径
- 左叶子之和
- 找树右下角的值
- 路径总和
- 二叉树的修改与构造
- 反转二叉树
- 最大二叉树
- 合并二叉树
- 从中序和前序遍历构造二叉树
- 从中序和后序遍历构造二叉树
- 二叉树公共祖先问题
- 二叉搜索树的最近公共祖先
- 二叉树的最近公共祖先
- 二叉搜索树的属性
- 二叉搜索树的搜索
- 二叉搜索树的验证
- 二叉搜索树的最小绝对差
- 二叉搜索树的众数
- 二叉搜索树转换成累加树
- 二叉搜索树的修改与构造
- 二叉树搜索树的插入
- 二叉树搜索树的删除
- 二叉树搜索树的修剪
- 有序数组生成二叉树搜索树
翻转二叉树
leetcode: 给定一棵二叉树的根节点 root，请左右翻转这棵二叉树，并返回其根节点。
js
var mirrorTree = function (root) {
function loop(root) {
if (root === null) return;
[root["left"], root["right"]] = [root["right"], root["left"]];
mirrorTree(root.left);
mirrorTree(root.right);
}
loop(root);
return root;
};var mirrorTree = function (root) {
function loop(root) {
if (root === null) return;
[root["left"], root["right"]] = [root["right"], root["left"]];
mirrorTree(root.left);
mirrorTree(root.right);
}
loop(root);
return root;
};从前序与中序遍历序列构造二叉树
leetcode: 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
// 根左右 [3,9,20,15,7]
// 左根右 [9,3,15,20,7]
var buildTree1 = function (preorder, inorder) {
if (inorder.length == 0) return null;
// 先序第一个就是 root
const root = new TreeNode(preorder[0]);
// root 在中序数组中的索引位置，
// 计算可知 root左树的节点个数 === mid
// 计算可知 root右树的节点个数 === inorder.length - mid - 1
const mid = inorder.indexOf(preorder[0]);
const l1 = preorder.slice(1, mid + 1); // 获取 root 左子树的 preorder 序列。
const l2 = inorder.slice(0, mid); // 获取 root 左子树的 inorder 序列。
root.left = buildTree(l1, l2);
// 同理
const r1 = preorder.slice(mid + 1); // 获取 root 右子树的 preorder 序列。
const r2 = inorder.slice(mid + 1); // 获取 root 右子树的 inorder 序列。
root.right = buildTree(r1, r2);
return root;
};/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
// 根左右 [3,9,20,15,7]
// 左根右 [9,3,15,20,7]
var buildTree1 = function (preorder, inorder) {
if (inorder.length == 0) return null;
// 先序第一个就是 root
const root = new TreeNode(preorder[0]);
// root 在中序数组中的索引位置，
// 计算可知 root左树的节点个数 === mid
// 计算可知 root右树的节点个数 === inorder.length - mid - 1
const mid = inorder.indexOf(preorder[0]);
const l1 = preorder.slice(1, mid + 1); // 获取 root 左子树的 preorder 序列。
const l2 = inorder.slice(0, mid); // 获取 root 左子树的 inorder 序列。
root.left = buildTree(l1, l2);
// 同理
const r1 = preorder.slice(mid + 1); // 获取 root 右子树的 preorder 序列。
const r2 = inorder.slice(mid + 1); // 获取 root 右子树的 inorder 序列。
root.right = buildTree(r1, r2);
return root;
};