力扣 106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如 给出

中序遍历 inorder [9,3,15,20,7]
后序遍历 postorder [9,15,7,20,3]
返回如下的二叉树

3

/
9 20
/
15 7

来源 力扣 LeetCode
链接 https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权 非商业转载请注明出处。

和105类似。就是找左右子树再递归。
突然好像有一点点悟了二叉树(p≧w≦q)

方法1 python

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val 0, left None, right None):
# self.val val
# self.left left
# self.right right
class Solution:
 def buildTree(self, inorder: List[int], postorder: List[int]) - TreeNode:
 def build(inorder,instart,inend,postorder,poststart,postend):
 if instart inend: return 
 var postorder[poststart]
 flag 0
 for i in range(instart,inend 1):
 if var inorder[i]:
 flag i
 break
 leftsize flag-instart
 root TreeNode(var)
 root.left build(inorder,instart,flag-1,postorder,postend leftsize-1,postend)
 root.right build(inorder,flag 1,inend,postorder,poststart-1,postend leftsize)
 return root
 return build(inorder,0,len(inorder)-1,postorder,len(postorder)-1,0)

方法2 java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val val;
 * this.left left;
 * this.right right;
class Solution {
 public TreeNode buildTree(int[] inorder, int[] postorder) {
 return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
 public TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
 if (inStart inEnd) {
 return null;
 // 根节点
 int rootVal postorder[postEnd];
 // 找到根节点在中序遍历中的索引
 int index 0;
 for (int i inStart; i inEnd; i ) {
 if (inorder[i] rootVal) {
 index i;
 break;
 // 左子树的节点个数
 int leftSize index - inStart;
 // 递归构造左右子树
 TreeNode root new TreeNode(rootVal);
 root.left build(inorder, inStart, index - 1, postorder, postStart, postStart leftSize - 1);
 root.right build(inorder, index 1, inEnd, postorder, postStart leftSize, postEnd - 1);
 return root;