Construct Binary Tree from Inorder and Postorder Traversal——LeetCode

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

题目大意:给定一个二叉树的中序和后续序列,构建出这个二叉树。

解题思路:首先后序序列的最后一个是根节点,然后在中序序列中找到这个节点,中序序列中这个节点左边的是根节点的左子树,右边的是右子树,由此递归构建出完整的树。

Talk is cheap:

    public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || postorder == null) {
return null;
}
int inLen = inorder.length;
int postLen = postorder.length;
if ((inLen == 0 && postLen == 0) || inLen != postLen) {
return null;
} TreeNode root = new TreeNode(postorder[postLen - 1]);
if (inLen == 1) {
return root;
}
int pos = 0;
for (int i = 0; i < inLen; i++) {
if (inorder[i] == postorder[postLen - 1]) {
pos = i;
break;
}
}
int[] inLeft = Arrays.copyOfRange(inorder, 0, pos);
int[] inRight = Arrays.copyOfRange(inorder, pos + 1, inLen);
int[] postLeft = Arrays.copyOfRange(postorder, 0, pos);
int[] postRight = Arrays.copyOfRange(postorder, pos, postLen - 1); root.left = buildTree(inLeft, postLeft);
root.right = buildTree(inRight, postRight);
return root;
}
上一篇:spring mvc 和junit 4集成的注意点


下一篇:BGP - 4,BGP的三张表