LeetCode(105):从前序与中序遍历序列构造二叉树
Medium!
题目描述:
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3 / \ 9 20 / \ 15 7
解题思路:
这道题要求用先序和中序遍历来建立二叉树,由于先序的顺序的第一个肯定是根,所以原二叉树的根节点可以知道,题目中给了一个很关键的条件就是树中没有相同元素,有了这个条件我们就可以在中序遍历中也定位出根节点的位置,并以根节点的位置将中序遍历拆分为左右两个部分,分别对其递归调用原函数。
C++解法一:
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { 13 return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1); 14 } 15 TreeNode *buildTree(vector<int> &preorder, int pLeft, int pRight, vector<int> &inorder, int iLeft, int iRight) { 16 if (pLeft > pRight || iLeft > iRight) return NULL; 17 int i = 0; 18 for (i = iLeft; i <= iRight; ++i) { 19 if (preorder[pLeft] == inorder[i]) break; 20 } 21 TreeNode *cur = new TreeNode(preorder[pLeft]); 22 cur->left = buildTree(preorder, pLeft + 1, pLeft + i - iLeft, inorder, iLeft, i - 1); 23 cur->right = buildTree(preorder, pLeft + i - iLeft + 1, pRight, inorder, i + 1, iRight); 24 return cur; 25 } 26 };
我们下面来看一个例子, 某一二叉树的中序和后序遍历分别为:
Preorder: 5 4 11 8 13 9
Inorder: 11 4 5 13 8 9
5 4 11 8 13 9 => 5
11 4 5 13 8 9 / \
4 11 8 13 9 => 5
11 4 13 8 9 / \
4 8
11 13 9 => 5
11 13 9 / \
4 8
/ / \
11 13 9
做完这道题后,大多人可能会有个疑问,怎么没有由先序和后序遍历建立二叉树呢,这是因为先序和后序遍历不能唯一的确定一个二叉树,比如下面五棵树:
1 preorder: 1 2 3
/ \ inorder: 2 1 3
2 3 postorder: 2 3 1
1 preorder: 1 2 3
/ inorder: 3 2 1
2 postorder: 3 2 1
/
3
1 preorder: 1 2 3
/ inorder: 2 3 1
2 postorder: 3 2 1
\
3
1 preorder: 1 2 3
\ inorder: 1 3 2
2 postorder: 3 2 1
/
3
1 preorder: 1 2 3
\ inorder: 1 2 3
2 postorder: 3 2 1
\
3
从上面我们可以看出,对于先序遍历都为1 2 3的五棵二叉树,它们的中序遍历都不相同,而它们的后序遍历却有相同的,所以只有和中序遍历一起才能唯一的确定一棵二叉树。
相关文章
- LeetCode刷题系列(4)
- 【LeetCode】均等概率问题,我有妙招!
- LeetCode周赛303,又见手速场……
- leetcode-103二叉树的锯齿形层序遍历「建议收藏」
- leetcode 647. 回文子串 js实现
- LeetCode 700. 二叉搜索树中的搜索
- LeetCode笔记:Biweekly Contest 89
- 前端工程师leetcode算法面试必备-二叉树深度广度遍历
- leetcode 160. 相交链表 js 实现
- 【day04】力扣(LeetCode)每日一刷[1306. 跳跃游戏 III ][703. 数据流中的第 K 大元素 ][1337. 矩阵中战斗力最弱的 K 行]
- leetcode刷题(126)——1289. 下降路径最小和 II
- Leetcode模块训练2
- javascript分类刷leetcode动态规划篇
- LeetCode - #74 搜索二维矩阵
- golang刷leetcode:买卖股票最佳时机
- JavaScript刷LeetCode拿offer-二叉树层序遍历篇5
- LeetCode-338-比特位计数