105/106-从先序与中序遍历构造二叉树

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

LeetCode-105

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

method 1: 递归

以先序遍历的第一个点作为分割点，分割中序遍历数组

直接传入数组的左右边界，就不用再构造，只是很多细节要注意，可以处理的数组范围是[preL, preR)以及[inL, inR)

TreeNode* traversal(vector<int>& pre, vector<int>& in, int preL, int preR, int inL, int inR) {
    if (preL >= preR) return nullptr;
    TreeNode *root = new TreeNode(pre[preL]);
    int idx;
    for (idx = inL; idx < inR; idx++) {
        if (in[idx] == root->val) {
            break;  // 找到中序遍历中对应节点的下标
        }
    }
    int leftLen = idx - inL;    // 计算左边长度
    root->left = traversal(pre, in, preL + 1, preL + 1 + leftLen, inL, idx);
    root->right = traversal(pre, in, preL + 1 + leftLen, preR, idx + 1, inR);
    return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = preorder.size();
    if (n == 0) return nullptr;
    return traversal(preorder, inorder, 0, n, 0, n);
}

可以用哈比表存中序遍历数组的下标，这样就不用去找了

unordered_map<int, int> hash;
TreeNode* dfs(vector<int>& pre, vector<int>& in, int preL, int preR, int inL, int inR) {
    if (preL >= preR) return nullptr;
    TreeNode *root = new TreeNode(pre[preL]);
    int idx = hash[root->val];
    int leftNum = idx - inL;
    root->left = dfs(pre, in, preL + 1, preL + 1 + leftNum, inL, idx);
    root->right = dfs(pre, in, preL + 1 + leftNum, preR, idx + 1, inR);
    return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = preorder.size();
    for (int i = 0; i < n; i++) {
        hash[inorder[i]] = i;
    }
    return dfs(preorder, inorder, 0, n, 0, n);
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$，哈比表要$O(n)$，递归的栈空间要$O(h)$，$h<n$

method 2: 迭代

i指向前序遍历数组，index指向中序遍历数组，一开始栈中只有根节点

• 如果栈顶元素与index指向的中序遍历数组元素不同，说明当前i指向的前序遍历的元素是栈顶元素的左节点
• 如果栈顶元素与index指向的元素相同，说明i指向的元素是栈顶元素或其某个祖先节点的右节点，所以如果两者相同就一直将栈顶元素弹出，直到不同的时候，说明当前i指向的元素就是最后弹出的那个节点的右节点

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    stack<TreeNode*> st;
    TreeNode *root = new TreeNode(preorder[0]);
    st.push(root);
    int index = 0;
    for (int i = 1; i < preorder.size(); i++) {
        TreeNode *node = st.top();
        if (inorder[index] != node->val) {  // 不同说明i指向的元素是栈顶节点的左节点
            node->left = new TreeNode(preorder[i]);
            st.push(node->left);
        } else {
            while (!st.empty() && inorder[index] == st.top()->val) {
                node = st.top();    // 一直弹出，并记录弹出的节点
                st.pop();
                index++;
            }
            node->right = new TreeNode(preorder[i]);    // i指向的元素就是最后一个弹出的节点的右节点
            st.push(node->right);
        }
    }
    return root;
}

---

LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

LeetCode-106

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

method: 递归

后序遍历的最后一个元素是根节点，用根节点来切割中序遍历，用3把中序遍历切割为[9]和[15,20,7]，以相同的数量切割后序遍历(除去最后一个元素)，切割为[9]和[15,7,20]，以此递归，直到后序遍历数组无元素

可以传数组长度

TreeNode* traversal(vector<int>& in, vector<int>& post, int inL, int inR, int postL, int postR) {
    if (inL >= inR) return nullptr;
    TreeNode *root = new TreeNode(post[postR - 1]); // 最后一个元素
    int idx = inL;
    for (; idx < inR; idx++) {
        if (in[idx] == root->val) break;
    }
    int leftLen = idx - inL;
    root->left = traversal(in, post, inL, idx, postL, postL + leftLen);
    root->right = traversal(in, post, idx + 1, inR, postL + leftLen, postR - 1);    // 去掉最后一个元素
    return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    int n = inorder.size();
    if (n == 0) return nullptr;
    return traversal(inorder, postorder, 0, n, 0, n);
}

---

LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

method

先序遍历的根节点后面是第一个左子树节点，找到该左子树节点在后序遍历中的位置，则后序遍历中第一个左子树节点及其前面的节点就都是左子树节点，就可以得到左子树的区间，剩下的就是右子树的区间，递归构建

TreeNode* dfs(vector<int>& pre, vector<int>& post, int preL, int preR, int postL, int postR) {
    if (preL >= preR) return nullptr;
    TreeNode *root = new TreeNode(pre[preL]);
    if (preL == preR - 1) return root;  // 因为后面会preL+1，如果只有一个元素就直接返回，不然会越界
    int idx = postL;
    for (; idx < postR; idx++) {
        if (post[idx] == pre[preL + 1]) break;
    }
    int leftNum = idx - postL + 1;  // 闭区间，[postL,idx]
    root->left = dfs(pre, post, preL + 1, preL + 1 + leftNum, postL, idx + 1);
    root->right = dfs(pre, post, preL + 1 + leftNum, preR, idx + 1, postR - 1);
    return root;
}
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
    int n = preorder.size();
    return dfs(preorder, postorder, 0, n, 0, n);
}