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:
每个元素访问一次生成一个结点，但每次访问时找mid可能需要n时间，时间复杂度O(n^2).
Ver.2
现在虽然不知道分界点, 但我们有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;
}
}