LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
程序员文章站
2022-06-18 17:54:00
...
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
题目描述
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
题目大意: 根据一个二叉树的先序遍历序列和中序遍历序列,构造出该二叉树。
解题思路
根据给定的先序遍历序列,可以知道根的值,然后根据该值在中序遍历中划分左右子树,直到子树为空。如给定的例子:
1. 根据先序序列,可知,根节点的值为 3。
2. 在中序序列中找到该值,就可以划分出左子树和右子树。
划分的子树:
3. 同理, 对左子树做同样的操作:
4. 对右子树做同样的操作:
AC 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
private:
// 根据先序遍历序列的 [preBeg, preBeg+size) 和 中序遍历的 [inBeg, inBeg+size) 构建二叉树的子树
TreeNode* buildTree(vector<int>& preorder, int preBeg,
vector<int>& inorder, int inBeg, int size)
{
if(size <= 0) return nullptr;
TreeNode* curNode = new TreeNode(preorder[preBeg]);
int inorderLeftTreeEnd = inBeg;
while(inorder[inorderLeftTreeEnd] != preorder[preBeg]) ++inorderLeftTreeEnd;
int leftTreeSize = inorderLeftTreeEnd - inBeg;
int rightTreeSize = (inBeg + size) - inorderLeftTreeEnd - 1;
curNode->left = buildTree(preorder, preBeg+1, inorder, inBeg, leftTreeSize);
curNode->right = buildTree(preorder, preBeg+1+leftTreeSize,
inorder, inorderLeftTreeEnd+1, rightTreeSize);
return curNode;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
return buildTree(preorder, 0, inorder, 0, preorder.size());
}
};
推荐阅读
-
LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
-
leetcode 随笔 Construct Binary Tree from Preorder and Inorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode(106)Construct Binary Tree from Inorder and Postorder Traversal
-
LeetCode 94. Binary Tree Inorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode106. Construct Binary Tree from Inorder and Postorder Traversal