LeetCode 106 leetcode

原题:

Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

题意：给你一个后序遍历和中序遍历的数组，要求构建二叉树

代码和思路：
【LeetCode 106】 后序遍历：就是先访问左子树------右子树 ------根节点所以后序遍历数组的最后一个个数就是根节点。

中序遍历：就是先访问左子树------根节点------右子树根节点在中间，左边是左子树，右边是右子树

[java]view plain copy

4
/\
27
/ \/ \
13 69

上面的二叉树为例子：
后序遍历的结果是：1326974
中序遍历的结果是：1234679可以看到4在最中间，2在13中间，7在69中间。这样就用迭代即可

代码跟105的基本一样，改少数几个地方即可

/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { return recursion(postorder.length-1,0,inorder.length-1,inorder,postorder); } private TreeNode recursion(int postLast,int inStart,int inEnd,int[] inorder, int[] postorder){ if(inStart > inEnd || postLast<0){ return null; }TreeNode root = new TreeNode(postorder[postLast]); int inIndex = 0; for(int i = inStart; i<=inEnd; i++){ if(inorder[i]==root.val){ inIndex = i; } } //左节点在后序遍历中的位置是 postLast-(inEnd-inIndex)-1 root.left = recursion(postLast-(inEnd-inIndex)-1,inStart,inIndex-1,inorder,postorder); //右节点在后序遍历中的位置是 postLast-1 root.right = recursion(postLast-1,inIndex+1,inEnd,inorder,postorder); return root; } }