leetCode 106.Construct Binary Tree from Inorder and Postorde

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:You may assume that duplicates do not exist in the tree.

思路：这题和上题类似，前序第一个是根节点，，后序遍历最后一个是根节点。其余步骤类似。

代码如下：

/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */public class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {/*** 1.根据后序遍历，先确定根节点* 2.然后在中序遍历中查找根节点，确定根节点在中序遍历的位置* 3.根据索引位置分割左右子树的前序和中序遍历* 4.递归求解根节点的左右子树*/if(postorder.length == 0 || inorder.length == 0)return null;TreeNode root = new TreeNode(postorder[postorder.length-1]);int k = 0;for(; k < inorder.length; k++){if(inorder[k] == postorder[postorder.length-1]){break;}}int[] p1 = Arrays.copyOfRange(postorder,0,k);int[] q1 = Arrays.copyOfRange(postorder,k,postorder.length-1);int[] p2 = Arrays.copyOfRange(inorder,0,k);int[] q2 = Arrays.copyOfRange(inorder,k+1,inorder.length);root.left = buildTree(p2,p1);root.right = buildTree(q2,q1);return root;}}

版权声明：本文为博主原创文章，未经博主允许不得转载。

痛苦留给的一切，请细加回味!苦难一经过去，苦难就变为甘美。