力扣105. 从前序与中序遍历序列构造二叉树

栈

• 思路：
  • 先序遍历：根、左子树、右子树；
  • 中序遍历：左子树、根、右子树；
  • 遍历先序遍历数组 prev，使用一个辅助栈缓存“根节点”；
  • 通过栈顶“根节点”与中序遍历数组 in 比较，确认是否到了“最左”节点；
    • 如果没有到最左节点，将 prev[idx] 节点挂到栈顶的左子树节点上，并且入栈；
    • 如果到了“最左”节点，出栈，直到不是“最左”节点，将节点挂到栈顶的右子树节点上；

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if (!preorder.size()) {return nullptr;}TreeNode* root = new TreeNode(preorder[0]);std::stack<TreeNode*> stk;stk.push(root);int in_idx = 0;for (int idx = 1; idx < preorder.size(); ++idx) {int pre_val = preorder[idx];TreeNode* node = stk.top();if (node->val != inorder[in_idx]) {node->left = new TreeNode(pre_val);stk.push(node->left);} else {while (!stk.empty() && (stk.top()->val == inorder[in_idx])) {node = stk.top();stk.pop();++in_idx;}node->right = new TreeNode(pre_val);stk.push(node->right);}}return root;}
};