LeetCode_Construct Binary Tree from Inorder and Postorder Traversal
LeetCode and from Tree Binary Traversal Construct
2023-09-11 14:15:00 时间
一.题目
Construct Binary Tree from Inorder and Postorder Traversal
Total Accepted: 33418 Total Submissions: 124726My Submissions
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Show Tags
Have you met this question in a real interview?
Yes
No
二.解题技巧
这道题和Construct Binary Tree from Preorder and Inorder Traversal类似,都是考察基本概念的,后序遍历是先遍历左子树。然后遍历右子树,最后遍历根节点。
做法都是先依据后序遍历的概念,找到后序遍历最后的一个值。即为根节点的值,然后依据根节点将中序遍历的结果分成左子树和右子树。然后就能够递归的实现了。
上述做法的时间复杂度为O(n^2),空间复杂度为O(1)。
三.实现代码
#include <iostream> #include <algorithm> #include <vector> /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ using std::vector; using std::find; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { private: TreeNode* buildTree(vector<int>::iterator PostBegin, vector<int>::iterator PostEnd, vector<int>::iterator InBegin, vector<int>::iterator InEnd) { if (InBegin == InEnd) { return NULL; } if (PostBegin == PostEnd) { return NULL; } int HeadValue = *(--PostEnd); TreeNode *HeadNode = new TreeNode(HeadValue); vector<int>::iterator LeftEnd = find(InBegin, InEnd, HeadValue); if (LeftEnd != InEnd) { HeadNode->left = buildTree(PostBegin, PostBegin + (LeftEnd - InBegin), InBegin, LeftEnd); } HeadNode->right = buildTree(PostBegin + (LeftEnd - InBegin), PostEnd, LeftEnd + 1, InEnd); return HeadNode; } public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if (inorder.empty()) { return NULL; } return buildTree(postorder.begin(), postorder.end(), inorder.begin(), inorder.end()); } };
四.体会
这道题主要考察的是基本概念。并没有非常复杂的算法在里面,能够算是对于二叉树的遍历的进一步理解。
版权全部,欢迎转载。转载请注明出处,谢谢
相关文章
- Leetcode 之Simplify Path(36)
- Java实现 LeetCode 836 矩形重叠(暴力)
- Java实现 LeetCode 796 旋转字符串 (水题)
- Java实现 LeetCode 532 数组中的K-diff数对(双指针,滑动窗口)
- Java实现LeetCode_0041_FirstMissingPositive
- 【LeetCode算法-38】Count and Say
- LeetCode(94):二叉树的中序遍历
- LeetCode(74):搜索二维矩阵
- 网络号 = IP和子网掩码的每位数AND 主机号 掩码取反与IP地址and运算
- [LeetCode] Patching Array
- [LeetCode] Bulls and Cows
- [LeetCode] Best Time to Buy and Sell Stock III
- [LeetCode] Two Sum
- LeetCode-809. 情感丰富的文字【双指针,简洁】
- ( “树” 之 BST) 108. 将有序数组转换为二叉搜索树 ——【Leetcode每日一题】
- 【LeetCode 22】括号生成
- 【LeetCode 8】字符串转换整数 (atoi)
- leetcode - Construct Binary Tree from Inorder and Postorder Traversal
- LeetCode 字母异位词分组(map解决)
- Leetcode 1460. 通过翻转子数组使两个数组相等
- LeetCode——Count and Say
- leetcode第一刷_Validate Binary Search Tree
- LeetCode 122 Best Time to Buy and Sell Stock II
- leetcode第一刷_Construct Binary Tree from Inorder and Postorder Traversal
- Leetcode:best_time_to_buy_and_sell_stock_II题解
- leetcode 38. Count and Say
- leetcode 121. Best Time to Buy and Sell Stock
- leetcode 122. Best Time to Buy and Sell Stock II