LeetCode Construct Binary Tree from Preorder and Inorder Traversal

LeetCode 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.


根据树的先序遍历和中序遍历结果,重构这棵树。

其实大学的时候就有这样的作业,如果在纸上做,还是很简单的,但要实现成代码,稍微有点难理清这里的关系。

我们先来看一个纸上的解题过程,假设有下面这样一棵树:

        3
     /     \
    9       20
  /  \     /   \
 1    2  15    17
  • 先序遍历结果为:3, 9, 1, 2, 20, 15, 17
  • 中序遍历结果为:1, 9, 2, 3, 15, 20, 17

首先我们可以根据先序遍历结果找到根节点3,然后在中序遍历中看看3所处的位置,那么3左边的就是左孩子节点,右边的就是右孩子节点。我们在中序遍历中看看3左边有3个节点,说明3的左子树共有3个节点,同理右子树有3个节点。所以我们在先序遍历中也能知道3后面的3个节点是左子树,再后面3个节点是右子树,这样就把两个遍历结果分成了两部分:

  • 先序遍历结果为:3, 9, 1, 2, 20, 15, 17
  • 中序遍历结果为:1, 9, 2, 3, 15, 20, 17

在红色部分递归就是3的左子树,在蓝色部分递归就是3的右子树。

纸上解题好说,但是代码实现,我开始还把自己搞糊涂了,代码很复杂,后来参考了这位大神的博客,代码好简洁易懂,赞一个:

class Solution {
private:
	TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int preL, int preR, int inL, int inR, unordered_map<int, size_t>& hash) {
		if (preL > preR || inL > inR)return NULL;
		TreeNode* root = new TreeNode(preorder[preL]);
		size_t idx = hash[root->val];
		root->left = dfs(preorder, inorder, preL + 1, idx - inL + preL, inL, idx - 1, hash);
		root->right = dfs(preorder, inorder, idx - inL + preL + 1, preR, idx + 1, inR, hash);
		return root;
	}

public:
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
		if (preorder.size() == 0)return NULL;
		unordered_map<int, size_t> hash;
		for (size_t i = 0; i < inorder.size(); ++i) {
			hash[inorder[i]] = i;
		}
		return dfs(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1, hash);
	}
};

本代码提交AC,用时16MS。

代码中有两点需要注意的,一是为了在中序遍历中快速找到根节点,提前对中序遍历结果hash了,因为题目中说了不会有重复元素;二是在dfs递归的时候,要算好下标的起止位置,一定不要弄错了,特别是preorder在左右子树中的起止位置。

Leave a Reply

Your email address will not be published. Required fields are marked *