LeetCode[106] Construct Binary Tree from Inorder and Postorder Traversal

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

分析:

本题是重建二叉树(后序加中序),跟重建二叉树(先序加中序)思路一样。

代码:

public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return rebuildTree(postorder, 0, postorder.length, inorder, 0, inorder.length);
}
TreeNode rebuildTree(int[] postorder, int begin1, int end1, int[] inorder, int begin2, int end2) {
if (begin1 == end1) return null;
TreeNode root = new TreeNode(postorder[end1 - 1]);
int inPos = find(inorder, begin2, end2, postorder[end1 - 1]);
int rightSize = end2 - inPos - 1;
root.right = rebuildTree(postorder, end1 - rightSize - 1, end1 - 1, inorder, inPos + 1, end2);
root.left = rebuildTree(postorder, begin1, end1 - rightSize - 1, inorder, begin2, inPos);
return root;
}
int find(int[] in, int begin2, int end2, int val) {
for (int i = begin2; i < end2; i++) {
if (in[i] == val)
return i;
}
return -1;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD's Blog All Rights Reserved.

访客数 : | 访问量 :