题目
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
思路
思路和[LeetCode]*105.Construct Binary Tree from Preorder and Inorder Traversal一样。
代码
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
int size = inorder.size();
if(size <= 0){
return nullptr;
}
return InPostBuildTree(inorder,postorder,0,size-1,size);
}
private:
TreeNode* InPostBuildTree(vector<int> &inorder,vector<int> &postorder,int inIndex,int postIndex,int size){
if(size <= 0){
return nullptr;
}
TreeNode* root = new TreeNode(postorder[postIndex]);
int index = 0;
for(int i = 0;i < size;++i){
if(postorder[postIndex] == inorder[inIndex+i]){
index = inIndex+i;
break;
}
}
int leftSize = index - inIndex;
int rightSize = size - leftSize - 1;
root->left = InPostBuildTree(inorder,postorder,inIndex,postIndex-1-rightSize,leftSize);
root->right = InPostBuildTree(inorder,postorder,index+1,postIndex-1,rightSize);
return root;
}
};
void PreOrder(TreeNode* root){
if(root){
cout<<root->val<<endl;
PreOrder(root->left);
PreOrder(root->right);
}
}
int main() {
Solution solution;
vector<int> inorder = {8,4,2,5,1,6,3,7};
vector<int> postorder = {8,4,5,2,6,7,3,1};
TreeNode* root = solution.buildTree(inorder,postorder);
PreOrder(root);
}
运行时间
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
leetcode的题目:Balanced Binary Tree
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
LeetCode.370.区间加法器解法:差分数组assert nums.length > 0;// 构造差分数组public void increment(i
Leetcode Chrome extension..zip,Leetcode Chrome扩展。
106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-sum (路径总和) 116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
LeetCode.swift.zip,很久以前,有一堆算法,他对斯威夫特略知一二。
LeetCode刷题题解.rar
leetcode - shuzu.html
LeetCode刷题手册.docx
LeetCode_book.rar