【leetcode】Construct Binary Tree from Inorder and Postorder Traversal

Question：

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

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

Anwser 1 ：

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *createTree(vector<int> &inorder, int inBeg, int inEnd, vector<int> &postorder, int postBeg, int postEnd)
{
if (inBeg > inEnd)  return NULL;

int root = postorder[postEnd];

int index;

for(int i = inBeg; i <= inEnd; i++)
if (inorder[i] == root)
{
index = i;
break;
}

int len = index - inBeg;
TreeNode *left = createTree(inorder, inBeg, index - 1, postorder, postBeg, postBeg + len - 1);
TreeNode *right = createTree(inorder, index + 1, inEnd, postorder, postBeg + len, postEnd - 1);

TreeNode *node = new TreeNode(root);
node->left = left;
node->right = right;

return node;
}

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (inorder.size() == 0) return NULL;

return createTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
};```

Anwser 2 ：

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
std::unordered_map<int,int> index_map;

void buildMap(vector<int> &inorder) {
index_map.clear();
for (int i = 0; i < inorder.size(); i++) {
index_map[inorder[i]] = i;
}
}

TreeNode *buildTreeInOrder(vector<int> &postorder, int post_offset, vector<int> &inorder, int in_offset, int len)
{
if (!len)  return NULL;

TreeNode *root = new TreeNode(postorder[post_offset]);
int i = index_map[postorder[post_offset]];

root->right = buildTreeInOrder(postorder, post_offset-1, inorder, in_offset, in_offset-i);
root->left = buildTreeInOrder(postorder, post_offset-(in_offset-i)-1, inorder, in_offset-(in_offset-i)-1, len-(in_offset-i)-1);

return root;
}

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (postorder.size() == 0 && inorder.size() == 0) {
return NULL;
}

buildMap(inorder);
return buildTreeInOrder(postorder, postorder.size()-1, inorder, inorder.size()-1, postorder.size());
}
};```

0 条评论

• 【leetcode】Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive ...

• 各种基本算法实现小结（五）—— 排序算法

* 选择排序 |____简单选择排序 |____堆排序 |____归并排序 * 交换排序 |____冒泡排序 |____快速排序 * 插入排序 |____直...

• 【leetcode】Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

• 【剑指offer：二叉搜索树的第k大节点】

这题LeetCode 230.二叉搜索树中第 K 小的元素差不多。只不过按照题目要求，这题是要按照从大到小的逆序顺序，访问二叉搜索树的元素。所以要改造下中序遍历...

• Java盲点解析

1 堆栈区别     Java的堆是一个运行时数据区,类的(对象从中分配空间。这些对象通过new、newarray、anewarray和multianewarr...

• 刷题第2篇：每日温度

各位小伙伴，大家好啊！今天是大年初二了。给大家拜年啦，祝各位新的一年里，有鼠不尽的幸福，工作顺利，爱情美满！

• 蓝桥杯之生命之数（dp dfs 邻接矩阵）

在X森林里，上帝创建了生命之树。 他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。 上帝要在这棵树内选出一个非空节点集...

Minikube是一个工具，可以在本地快速运行一个单点的Kubernetes，仅用于尝试Kubernetes或日常开发的用户使用。部署地址：https://ku...

• GR运维手册 - 第一册 苦海岸边，GR的基础知识

作者简介： ? 刘伟 云和恩墨开源解决方案事业部首席架构师 多年一线互联网企业DBA经历，对MySQL、NoSQL，PostgreSQL等各类开源数据库均有涉猎...

• Centos7.2/7.3集群安装Kubernetes 1.8.4 + Dashboard

1.环境配置 结点数量：3 结点系统：CentOS 7.2 / 7.3 ---- 2.效果展示 ? ? ---- 3.搭建Kubernetes环境【1】 3.1...