根据前序和中序（后序和中序）遍历构造树 #算法#

梦飞

发布于 2022-06-23 11:22:11

2410

发布于 2022-06-23 11:22:11

原题如下

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:

思路

（1）前序序列的第一个元素一定是根节点；（2）中序序列中根节点左边为左子树的中序序列，右边为右子树的中序序列；（3）根据根节点在中序序列中的位置，又可在前序序列中得到左子树的前序序列和右子树的前序序列；（4）用相同的原理又能分别找出左右子树的根节点；（5）根节点的左子节点为左子树的根节点，右子节点为右子树的根节点；（6）再用相同的方法找出子节点的左右子节点；如此递归下去，直到最终序列为空。

代码

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    	if(preorder.empty()) return NULL;
    	int size = preorder.size();
    	int root_value = preorder[0];
        TreeNode* root = new TreeNode(root_value);
        vector<int> pre_left, in_left, pre_right, in_right;
        int i;
        for(i = 0; i < size; i++){
        	int value = inorder[i];
        	if(value == root_value) break;
        	in_left.push_back(value);
        	pre_left.push_back(preorder[i + 1]);
		}
		for(i++; i < size; i++){
			in_right.push_back(inorder[i]);
			pre_right.push_back(preorder[i]);
		}
        TreeNode* left = buildTree(pre_left, in_left);
        TreeNode* right = buildTree(pre_right, in_right);
        root->left = left;
        root->right = right;
        return root;
    }
};

后序和中序

思路类似，只不过根节点在postorder的末尾，代码如下：

class Solution {
public:
    TreeNode* buildTree(vector<int>& postorder, vector<int>& inorder) {
    	if(postorder.empty()) return NULL;
    	int size = postorder.size();
    	int root_value = postorder[size - 1]; // 这里不同
        TreeNode* root = new TreeNode(root_value);
        vector<int> post_left, in_left, post_right, in_right;
        int i;
        for(i = 0; i < size; i++){
        	int value = inorder[i];
        	if(value == root_value) break;
        	in_left.push_back(value);
        	post_left.push_back(postorder[i]); // 这里不同
		}
		for(i++; i < size; i++){
			in_right.push_back(inorder[i]);
			post_right.push_back(postorder[i - 1]); // 这里不同
		}
        TreeNode* left = buildTree(post_left, in_left);
        TreeNode* right = buildTree(post_right, in_right);
        root->left = left;
        root->right = right;
        return root;
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-10-12，如有侵权请联系 cloudcommunity@tencent.com 删除

binary