LeetCode106. 从中序与后序遍历序列构造二叉树
题目来源:
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
题目描述:
代码如下:
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder, postorder, 0, inorder.length - 1, postorder.length - 1);
}
public TreeNode buildTree(int[] inorder, int[] postorder, int inStart, int inEnd, int postEnd) {
if (inStart > inEnd)
return null;
TreeNode root = new TreeNode(postorder[postEnd]);
int index = 0;
for (int i = inEnd; i >= inStart; i--) {
if (root.val == inorder[i]) {
index = i;
break;
}
}
root.right = buildTree(inorder, postorder, index + 1, inEnd, postEnd - 1);
root.left = buildTree(inorder, postorder, inStart, index - 1, postEnd - 1 + index - inEnd);
return root;
}
}