翻转二叉树
leetcode easy：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
js
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
code：
js
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function (root) {
if (!root) return null;
let left = root.left;
root.left = invertTree(root.right);
root.right = invertTree(left);
return root;
};
从中序与后序遍历序列构造二叉树
leetcode：给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
js
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
思路：首先推导
js
var buildTree = function (inorder, postorder) {
if (!inorder.length || postorder.length) return null;
// inorder 左根右 postorder 左右根
// 推导根 postorder[postorder.length - 1]
let rootValue = postorder[postorder.length - 1];
const root = new TreeNode(rootValue);
root.left = buildTree(leftInoder, leftPostorder);
root.right = buildTree(rightInoder, rightPostorder);
return root;
};
js
function TreeNode(val, left, right) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
/**
* 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[]} inorder
* @param {number[]} postorder
* @return {TreeNode}
*/
var buildTree = function (inorder, postorder) {
if (!inorder.length || !postorder.length) return null;
// inorder 左根右 postorder 左右根
// 推导根 postorder[postorder.length - 1]
const root = new TreeNode(postorder[postorder.length - 1]);
// 分割点
const index = inorder.findIndex((v) => root.val === v);
// 左子树的中序遍历
const leftInroder = inorder.slice(0, index);
// 左子树的后续遍历
const leftPostorder = postorder.slice(0, index);
// 右子树的中序遍历
const rightInroder = inorder.slice(index + 1);
// 右子树的后续遍历
const rightPostorder = postorder.slice(index, postorder.length - 1);
root.left = buildTree(leftInroder, leftPostorder);
root.right = buildTree(rightInroder, rightPostorder);
return root;
};
重建二叉树
leetcode: 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
js
Input: (preorder = [3, 9, 20, 15, 7]), (inorder = [9, 3, 15, 20, 7]);
Output: [3, 9, 20, null, null, 15, 7];
js
var buildTree = function (preorder, inorder) {
if (!preorder.length) return null;
let root = new TreeNode(preorder[0]);
// 分割点
let index = inorder.findIndex((v) => v === root.val);
// first index = 1;
// preorder 根左右 [右，根，左]
// inorder 左根右 [左, 根, 右]
root.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index));
root.right = buildTree(preorder.slice(index + 1), inorder.slice(index + 1));
return root;
};
最大二叉树
力扣题目地址 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
- 二叉树的根是数组中的最大元素。
- 左子树是通过数组中最大值左边部分构造出的最大二叉树。
- 右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
js
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
js
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var constructMaximumBinaryTree = function (nums) {
if (nums.length == 0) return null;
let maxNum = Math.max(...nums);
let index = nums.indexOf(maxNum);
return new TreeNode(
maxNum,
constructMaximumBinaryTree(nums.slice(0, index)),
constructMaximumBinaryTree(nums.slice(index + 1))
);
};
合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
注意: 合并必须从两个树的根节点开始。
js
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
js
var mergeTrees = function (root1, root2) {
if (!root1) return root2;
if (!root2) return root1;
return new TreeNode(root1.val + root2.val, mergeTrees(root1.left, root2.left), mergeTrees(root1.right, root2.right));
};