Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

Thoughts

根据二叉树的先序和中序遍历的结果还原二叉树，每个结点的值都是唯一的。由于树的递归定义，它的左子树可以通过左子树的坐标范围得到，右子树可以通过右子树坐标范围得到。前序第一个结点一定是root；而中序知道root前边肯定是左树，因此可以得到左子树的size，也就知道了pre-order中左子树坐标范围，它后面的就是右子树了。

Code

/*
 * @lc app=leetcode id=105 lang=cpp
 *
 * [105] Construct Binary Tree from Preorder and Inorder Traversal
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *dfs(vector<int> &preorder, int p_s, int p_e, vector<int> &inorder, int i_s, int i_e) {
        if (p_s > p_e) return nullptr;
        const auto root = preorder[p_s++];
        TreeNode *res = new TreeNode(root);
        int lsize = 0;
        for (int i = i_s; i <= i_e; ++i) {
            if (inorder[i] == root) {
                lsize = i - i_s;
                break;
            }
        }
        
        res->left = dfs(preorder, p_s, p_s + lsize - 1, inorder, i_s, i_s + lsize - 1);
        res->right = dfs(preorder, p_s + lsize, p_e, inorder, i_s + lsize + 1, i_e);
        return res;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return dfs(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
};
// @lc code=end

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode helper(int[] preorder, int pstart, int pend, int[] inorder, int instart, int inend) {
        if (pstart > pend || instart > inend) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[pstart]);
        int inNodePos = -1;
        for (int i = 0; i < inend - instart + 1; i++) {
            if (inorder[instart + i] == preorder[pstart]) {
                inNodePos = i; // 4
                break;
            }
        }
        node.left = helper(preorder, pstart + 1, pstart + inNodePos, inorder, instart, instart + inNodePos - 1); // 1 - 4, 0 - 3
        node.right = helper(preorder, pstart + inNodePos + 1, pend, inorder, instart + inNodePos + 1, inend); // 5 - 6, 5 - 6

        return node;
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
}

Analysis

Errors:

1. 在找前序中分界点时刚开始没想到利用长度

每个元素访问一次生成一个结点，但每次访问时找mid可能需要n时间，时间复杂度O(n^2).

Ver.2

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34555/?page=1 假设知道pre-order的分界处在哪, 中( ..., 左末)( 右1..., 右...). 那我们可以通过一遍Pre-order traversal建树. 栈内存当前的path, 当左子树建好后, 依次把左子树结点从stack中pop, 把中右设成右1, 中抛出, 继续对右1(为右子树的root)执行此过程.

现在虽然不知道分界点, 但我们有in-order: (..., 左末, ...)中(...右...), 同样跑Pre-order, stack存path, cur为当前dfs/backtracing的树节点. 当遇到左末点时我们知道左子树已经结束, 且左末前面的点已经在建立更sub的tree时已经抛出了, 因此直接把中抛出, 如果右1存在, 进入右1. 不存在则继续顺着往上抛出, 知道遇到有右一的(in-order[j] != cur).

 /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]), cur = root;
        for (int i = 1, j = 0; i < preorder.length; i++) {
            if (cur.val != inorder[j]) {
                cur.left = new TreeNode(preorder[i]);
                stack.push(cur);
                cur = cur.left;
            } else {
                j++;
                while (!stack.isEmpty() && stack.peek().val == inorder[j]) {
                    cur = stack.pop();
                    j++;
                }
                cur = cur.right = new TreeNode(preorder[i]);
            }
        }
        return root;
    }
}