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从前序
java java_leetcode题解之Construct Binary Tree from String.java
14. **重建二叉树**(Construct Binary Tree from Inorder and Postorder Traversal / Preorder Traversal) - 知识点:二叉树,递归,序列化与反序列化 - 解题策略:根据中序和后序/前序遍历序列,通过递归构建...
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/...
js js_leetcode题解之106-construct-binary-tree-from-inorder
python python_leetcode题解之106_Construct_Binary_Tree_from_Inorder
java java_leetcode题解之Construct String from Binary Tree.java
java java_leetcode-105-construct-binary-tree-from-preorder-and-inorde
js js_leetcode题解之105-construct-binary-tree-from-preorder
python python_leetcode题解之105_Construct_Binary_Tree_from_Preorder
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
Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. Find Minimum in Rotated Sorted Array 斐波那契数列 509. Fibonacci Number 跳台阶 70. Climbing Stairs 变态跳...
1. 二叉搜索树(Binary Search Tree,简称BST): 二叉搜索树是一种特殊的二叉树,其左子树上所有节点的值均小于它的根节点的值,右子树上所有节点的值均大于它的根节点的值。这种性质使得二叉搜索树在搜索、插入和...
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 ...