木又的第118篇leetcode解题报告
二叉树
类型第8篇解题报告
leetcode第105题:从前序与中序遍历序列构造二叉树
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
【题目】
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
【思路】
前序遍历的顺序是根左右;中序遍历的顺序是左根右。(前序、中序、后序遍历的顺序是访问根节点的顺序)
那么前序遍历的一个元素e,在中序遍历中找到其位置,那么该位置前的元素位于左子树上,该位置后的元素位于右子树上,以此递归。
举例来说,假设前序遍历为[1,2,3],后序遍历为[2,3,1]。
对于前序遍历第1个节点1,在中序遍历中找到其位置(第3个节点),那么[2,3](中序遍历为[2,3])位于根节点1的左子树上;
接着递归遍历前序遍历[2,3]中第一个节点2,在中序遍历中找到其位置(第1个节点),那么[3]位于该节点的右子树上;
接着递归遍历前序遍历[3]中第一个节点……
(python和c++的实现方式稍有不同,python直接生成子树的遍历顺序,c++通过下标来得到子树的遍历顺序)
【代码】
python版本
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
# 根左右 PK 左根右
if len(preorder) == 0:
return None
root = TreeNode(preorder[0])
num = inorder.index(preorder[0])
left_preorder = preorder[1:num+1]
right_preorder = preorder[num+1:]
left_inorder = inorder[:num]
right_inorder = inorder[num+1:]
self.build(root, left_preorder, left_inorder, right_preorder, right_inorder)
return root
def build(self, node, left_preorder, left_inorder, right_preorder, right_inorder):
if len(left_preorder) != 0:
node.left = TreeNode(left_preorder[0])
num = left_inorder.index(left_preorder[0])
self.build(node.left, left_preorder[1:num+1], left_inorder[:num], left_preorder[num+1:], left_inorder[num+1:])
if len(right_preorder) != 0:
node.right = TreeNode(right_preorder[0])
num = right_inorder.index(right_preorder[0])
self.build(node.right, right_preorder[1:num+1], right_inorder[:num], right_preorder[num+1:], right_inorder[num+1:])
C++版本
/**
* 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 {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode* root = new TreeNode(0);
build(root, true, preorder, 0, inorder, 0, preorder.size()-1, preorder.size()-1);
return root->left;
}
void build(TreeNode* node, bool left, vector<int>& preorder, int start1, vector<int>& inorder, int start2, int end1, int end2){
int place = 0;
if(start1 <= end1 && start2 <= end2){
if(left){
node->left = new TreeNode(preorder[start1]);
node = node->left;
}else{
node->right = new TreeNode(preorder[start1]);
node = node->right;
}
for(place = start2; place <= end2; place++){
if(inorder[place] == preorder[start1])
break;
}
build(node, true, preorder, start1+1, inorder, start2, end1, place-1);
build(node, false, preorder, start1+(place-start2)+1, inorder, place+1, end1, end2);
}
}
};