LeetCode 题解（155）: Construct Binary Tree from Inorder and Postorder Traversal

本文主要是介绍LeetCode 题解（155）: Construct Binary Tree from Inorder and Postorder Traversal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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

Note:
You may assume that duplicates do not exist in the tree.

题解：

递归。

C++版：

class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size() == 0 || postorder.size() == 0)return NULL;int rootVal = postorder[postorder.size() - 1];TreeNode* root = new TreeNode(rootVal);int i = 0;while(inorder[i] != rootVal) {i++;}root->left = findRoot(inorder, 0, i - 1, postorder, 0, i - 1);root->right = findRoot(inorder, i + 1, inorder.size() - 1, postorder, i, inorder.size() - 2);return root;}TreeNode* findRoot(vector<int>& inorder, int start1, int end1, vector<int>& postorder, int start2, int end2) {if(start1 > end1)return NULL;else if(start1 == end1) {TreeNode* root = new TreeNode(inorder[start1]);return root;}else {TreeNode* root = new TreeNode(postorder[end2]);int i = start1;while(inorder[i] != postorder[end2])i++;root->left = findRoot(inorder, start1, i - 1, postorder, start2, start2 + i - start1 - 1);root->right = findRoot(inorder, i + 1, end1, postorder, start2 + i - start1, start2 - start1 + end1 - 1);return root;}}
};

Java版；

public class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if(inorder.length == 0 || postorder.length == 0)return null;int i = 0;while(inorder[i] != postorder[postorder.length-1])i++;TreeNode root = new TreeNode(inorder[i]);root.left = findRoot(inorder, 0, i - 1, postorder, 0, i - 1);root.right = findRoot(inorder, i + 1, inorder.length - 1, postorder, i, postorder.length - 2);return root;}public TreeNode findRoot(int[] inorder, int start1, int end1, int[] postorder, int start2, int end2) {if(start1 > end1)return null;else if(start1 == end1) {TreeNode root = new TreeNode(inorder[start1]);return root;} else {int i = start1;while(inorder[i] != postorder[end2])i++;TreeNode root = new TreeNode(inorder[i]);root.left = findRoot(inorder, start1, i - 1, postorder, start2, start2 + i - 1 - start1);root.right = findRoot(inorder, i + 1, end1, postorder, start2 + i - start1, start2 - start1 + end1 - 1);return root;}}
}

Python版：

class Solution:# @param {integer[]} inorder# @param {integer[]} postorder# @return {TreeNode}def buildTree(self, inorder, postorder):if len(inorder) == 0 or len(postorder) == 0:return Nonei = 0while inorder[i] != postorder[len(postorder) - 1]:i += 1root = TreeNode(inorder[i])root.left = self.findRoot(inorder, 0, i - 1, postorder, 0, i - 1)root.right = self.findRoot(inorder, i + 1, len(inorder) - 1, postorder, i, len(postorder) - 2)return rootdef findRoot(self, inorder, start1, end1, postorder, start2, end2):if start1 > end1:return Noneelif start1 == end1:return TreeNode(inorder[start1])else:i = start1while inorder[i] != postorder[end2]:i += 1root = TreeNode(inorder[i])root.left = self.findRoot(inorder, start1, i - 1, postorder, start2, start2 + i - 1 - start1)root.right = self.findRoot(inorder, i + 1, end1, postorder, start2 + i - start1, start2 - start1 - 1 + end1)return root

这篇关于LeetCode 题解（155）: Construct Binary Tree from Inorder and Postorder Traversal的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---