Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
/** * 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 *buildTree(vector<int> &inorder, vector<int> &postorder) { if(inorder.size() != postorder.size()) return NULL; int n = inorder.size(); return build(inorder, 0, postorder, n-1, n); } TreeNode *build(vector<int> &io, int inStart, vector<int> &po, int postEnd, int len) { if(inStart < 0 || inStart + len > io.size() || postEnd >= po.size() || postEnd - len < -1 || len < 1) { return NULL; } int rootVal = po[postEnd]; int i = inStart; while(io[i] != rootVal) ++i; TreeNode *root = new TreeNode(rootVal); int leftLen = i - inStart; int rightLen = len - leftLen - 1; root->right = build(io, i+1, po, postEnd - 1, rightLen); root->left = build(io, inStart, po, postEnd - rightLen - 1, leftLen); return root; } };
欢迎关注微信公众号——计算机视觉:
相关推荐
Construct Binary Tree from Inorder and Postorder Traversa.根据先序后续构建二叉树
Construct Binary Tree from Preorder and Inorder Traversal 根据先序,中序建立二叉树
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
Construct Binary Tree from Inorder and Postorder Traversal 二叉查找树 Unique Binary Search Trees Unique Binary Search Trees II Validate Binary Search Tree Convert Sorted Array to Binary Search Tree ...
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-sum (路径总和) 116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点
lru缓存leetcode LeetCode_Note leetcode 个人笔记 ...[106_construct-binary-tree-from-inorder-and-postorder-traversal.cpp] [107_binary-tree-level-order-traversal-ii.cpp] [108_convert-sorted
leetcode 跳跃 Algorithm 算法题解: 包括书籍算法, 程序员算法面试指南, 还有leetcode算法题 ...construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-right-pointers-in-eac
Construct Optimal Binary Search Tree by Using Greedy Algorithm
Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. Find Minimum in Rotated Sorted Array 斐波那契数列 509. Fibonacci Number 跳台阶 70. Climbing Stairs 变态跳...
No prior experience is required.Game Development with Construct 2 teaches you to create 12 different game projects from a variety of genres, including car racing and tower defense to platformer and ...
to construct binary codes for users and items such that the preference of users over items can be accurately preserved by the Hamming distance between their respective binary codes. By using two loss ...
二叉树的实现代码 /*LinkTree.h*/ typedef int DataType; //这样定义意味着节点中能放一个整数,但如果是非叶子节点则可以解读为对应的操作符的ascii ...void inOrder( BinTree t); //travel in order
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 2 题目描述 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序...
concerning 345 burglars and 310 violent offenders in Nottinghamshire, England. The most important observable features of offenders were sex, ethnicity, age, height, build, hair color, hair length, and...
language testing 权威刊物文章 可供语言测试与学习者使用。
The frequency's must be listed, in order, from largest (at the top) to smallest (at the bottom) Then, using the Huffman algorithm, construct the optimal prefix binary code for the table. The Huffman ...
内含大量实例,来自多个知名算法测试平台的题目,还有讲解。
Biomimicry uses our scientific understanding of biological systems to exploit ideas from nature in order to construct some technology. In this book, we focus on how to use biomimicry of the functional...
The methodology used to construct tree structured rules is the focus of this monograph. Unlike many other statistical procedures, which moved from pencil and paper to calculators, this text's use of ...