Construct Binary Tree 系列

LeetCode 题解

题目的意思是根据已有二叉树的两种遍历顺序序列逆向还原出已有的二叉树

树的三种遍历方式

前序遍历 (preorder) ：中 - 左 - 右
中序遍历 (inorder) : 左 - 中 - 右
后序遍历 (postorder) : 左 - 右 - 中

思路

根据序列对应的遍历方式来进行分治构造二叉树

前序遍历：(根节点) (左子树节点 …. )(右子树节点 ….) 中序遍历：(左子树节点 ….) (根节点) (右子树节点 ….) 后序遍历：(左子树节点 ….) (右子树节点 ….) (根节点)

总有一个序列是我们可以立刻得到根节点的，得到根节点后，根据根节点分割出左子树的序列和右子树的序列，递归构造二叉树即可解决

例如：前序 + 中序

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    return createTree(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
}

TreeNode* createTree(vector<int>& preorder, vector<int>& inorder, int ps, int pe, int is, int ie) {
    if (ps > pe || is > ie) return NULL;
	// 前序找到根节点
    int rootVal = preorder[ps];
    int idx;
	// 通过根节点值找到中序的切分点
    for(idx=is;idx<=ie&&inorder[idx]!=rootVal;++idx) {}

    TreeNode* troot = new TreeNode(rootVal);

	// 切分递归构造左子树
    troot->left = createTree(preorder, inorder, ps+1, idx-is+ps, is, idx-1);
	// 切分递归构造右子树
    troot->right = createTree(preorder, inorder, pe-(ie-idx)+1, pe, idx+1, ie);
    return troot;
}

中序 + 后序同理，只要找到根节点，然后就能划分中序序列进而通过元素个数划分后序进行递归构造

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    return createTree(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
}

TreeNode* createTree(vector<int>& inorder, vector<int>& postorder, int is, int ie, int ps, int pe) {
    if (is > ie || ps > pe) return NULL;
    int rootVal = postorder[pe];
    int idx;
    for(idx=is;idx<=ie&&inorder[idx]!=rootVal;++idx) {}

    TreeNode* troot = new TreeNode(rootVal);
    troot->left = createTree(inorder, postorder, is, idx-1, ps, ps+idx-is-1);
    troot->right = createTree(inorder, postorder, idx+1, ie, ps+idx-is, pe-1);
    return troot;
}

前序 + 后序，都能够找到根节点，但是划分的时候需要注意一下边界，这里我们取前序根节点的下一个元素的值在后序的位置来进行后序的划分，然后再根据后序划分的长度来等长划分前序，与前面的类型同理

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        int len = post.size();
        for (int i = 0; i < len; i++) m[post[i]] = i;
        return createTree(pre, post, 0, pre.size()-1, 0, post.size()-1);
    }

    TreeNode* createTree(vector<int>& pre, vector<int>& post, int pre_st, int pre_e, int po_st, int po_e) {
        if (pre_st > pre_e || po_st > po_e) return NULL;
        TreeNode* troot = new TreeNode(pre[pre_st]);
		// 边界条件：划分到只有根的时候直接返回
        if (pre_st == pre_e) return troot;
        int post_idx=m[pre[pre_st+1]];
        
        troot->left = createTree(pre, post, pre_st+1, pre_st+1+post_idx-po_st, po_st, post_idx);
        troot->right = createTree(pre, post, pre_st+2+post_idx-po_st, pre_e, post_idx+1, po_e-1);
        return troot;
    }
    unordered_map<int, int> m;
};

#递归 #分治 #tree

Combination Sum 系列 Decode Ways 系列