leetcode 106
思路
中序遍历：左中右
后序遍历：左右中
那么可以知道后序遍历的最后一个值一定是根节点，因为最后遍历中间节点，中间节点就是根节点，知道中间点，就能将中序数组进行切割，以中间节点为分割点，左边就是左子树，右边就是右子树，也就是题目中的inorder可以切割为leftTree = [9] rightTree = [15,20,7]
然后再切割后序遍历，右子树是左右中，左子树的长度是和中序遍历左子树的长度是一样的，所以也可以进行切割leftTree = [9] rightTree = [15,7,20]
然后对于左子树和右子树，继续进行递归遍历，知道右子树只有一个值的时候，说明已经到叶子节点，所以结束递归，最终把root值返回
实现
class TreeNode {constructor(val) {this.val = val;this.left = null;this.right = null;}
}
var buildTree = function (inorder, postorder) {const deep = (inorder, postorder) => {if(!postorder.length) return null;if (postorder.length === 1) {return new TreeNode(postorder[0])}// 根节点是后序数组的最后一位const rootVal = postorder[postorder.length - 1]let root = new TreeNode(rootVal)// 切割前序数组，获取左子树节点和右子树节点const index = inorder.indexOf(rootVal)// 前序左孩子const inorderarr1 = inorder.slice(0, index)// 前序右孩子const inorderarr2 = inorder.slice(index + 1)// 切割后序数组，后序数组的左子树，跟前序的左孩子长度相等const postorderarr1 = postorder.slice(0, inorderarr1.length)const postorderarr2 = postorder.slice(inorderarr1.length, postorder.length - 1)root.left = deep(inorderarr1, postorderarr1)root.right = deep(inorderarr2, postorderarr2)return root;}return deep(inorder, postorder)
};
扩展
除了可以使用中序和后序来确定二叉树，使用前序和中序也可以确定一棵二叉树，也是同样的方法
leetcode 105 从前序与中序遍历序列构造二叉树
前序：中左右
中序：左中右
那么前序的第一个值就是根节点，也同样可以把中序的左子树和右子树拆分开
但是⚠️：前序和后序不能确定一棵二叉树
前序：中左右
后序：左右中
那么我们知道前序的第一个数是根节点，后序的最后一个数是根节点，但是前序和后序的左右子树都挨着的，我们无法进行拆分，所以不能解析出来二叉树
前序中序构造二叉树实现
class TreeNode {constructor(val) {this.val = val;this.left = null;this.right = null;}
}
var buildTree = function (preorder, inorder) {if (!preorder) return null;const deep = (preorder, inorder) => {if(!preorder.length) return null;if (preorder.length === 1) {return new TreeNode(preorder[0])}const rootVal = preorder[0]let root = new TreeNode(rootVal)// 中序切割const index = inorder.indexOf(rootVal);// 中序左子树const inorderArr1 = inorder.slice(0, index)// 中序右子树const inorderArr2 = inorder.slice(index + 1)// 前序切割const preorderArr1 = preorder.slice(1, 1 + inorderArr1.length)const preorderArr2 = preorder.slice(1 + inorderArr1.length)root.left = deep(preorderArr1, inorderArr1)root.right = deep(preorderArr2, inorderArr2);return root;}return deep(preorder, inorder)
};
