09
25

发表于 • • 被 617 人看爆

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

老题目了，已知后序遍历序列和前序遍历序列以后，都能够知道一棵树的根结点位置，前序遍历在序列第一个位置，后序遍历在序列第二个位置。
确定了根结点的位置和值以后，遍历中序遍历，比较中序遍历序列中与根结点值相同的值，就找到根结点在中序遍历的位置，此时中序遍历根结点左边即为左子树，右边即为右子树，递归的去查找左子树和右子树的根节点，并挂到根节点的左右孩子指针上即可。

代码：

class Solution {
public:
    /**
     根据中序和后序遍历构造二叉树 
     后序遍历的最后一个节点是树的根节点，根据这个查找到中序遍历的根节点
     
     **/
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int size = (int)inorder.size();
        return getRoot(0, size-1, 0, size-1, inorder, postorder);
    }
    
    // 标记当前树在中序和后序的位置
    TreeNode* getRoot(int inLeft, int inRight, int postLeft, int postRight,
                      vector<int>& inorder, vector<int>& postorder){
        if (inLeft > inRight) {
            return nullptr;
        }
        int rootVal = postorder[postRight]; // 根节点的值
        int k = inLeft; // k指向根节点在中序的位置
        for (; k <= inRight; ++k) {// 查找在中序遍历的位置
            if (inorder[k] == rootVal) {
                break;
            }
        }
        TreeNode* tmp = new TreeNode(rootVal);
        int leftTreeNum = k - inLeft;
        tmp->left = getRoot(inLeft, k-1, postLeft, postLeft + leftTreeNum-1, inorder, postorder);
        tmp->right = getRoot(k+1, inRight, postLeft+leftTreeNum, postRight-1, inorder, postorder);
        return tmp;
    } 
};
分享到：