本文主要是介绍Leetcode面试经典150题-106.从中序和后序序列构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解法都在代码里，不懂就留言或者私信
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/**解这个题你首先要知道二叉树的中序和后序遍历有啥特性中序：先左子树，后根，然后右子树后序：先左孩子，后右孩子，然后根一般二叉树构造这种问题我们首要的是先找到根在哪，通过中序是找不到根的。你要先通过后序找到根（最后那个），然后在中序中找根的位置，中序中根之前的是左子树，根之后的是右子树反正这么递归的搞，一会就出来了 */public TreeNode buildTree(int[] inorder, int[] postorder) {return buildTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);}/**我们这里调用这个函数的前提是inStart~inEnd和postStart~postEnd长度一定相同，不然没有任何意义这个函数的含义是从inOrder的inStart~inEnd和postOrder的postStart~postEnd构造二叉树并返回根*/public TreeNode buildTree(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {/**如果就一个元素，那毫无疑问就是当前的根*/if(inStart == inEnd) {return new TreeNode(inorder[inStart]);}if(inStart > inEnd) {return null;}/**否则把postEnd位置作为根*/int rootValue = postorder[postEnd];int rootIndex = -1;for(int i = inStart; i <= inEnd; i++) {if(inorder[i] == rootValue) {rootIndex = i;break;}}/**构造当前的根节点 */TreeNode root = new TreeNode(rootValue);/**左子树是中序序列中rootIndex之前的部分，右子树是中序序列中rootIndex之后的部分后序序列也要取同等长度,左子树的长度是rootIndex-inStart这里一定要注意右子树的结束是postEnd-1而不是postEnd*/root.left = buildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + (rootIndex-inStart)-1);root.right = buildTree(inorder, postorder, rootIndex + 1, inEnd, postStart + (rootIndex-inStart), postEnd-1);return root;}
}递归解法可能常数时间比较高，只能保证时间复杂度是O(n)
这篇关于Leetcode面试经典150题-106.从中序和后序序列构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
