上海建设工程安全监理网站,设计网站 杭州,建站公司主要做那些业务,加强局网站建设栈
思路#xff1a; 思路与 力扣105. 从前序与中序遍历序列构造二叉树 相同#xff1b;差异的地方#xff1a; 从后序遍历数组尾部向前遍历#xff1b;#xff08;根节点在尾部#xff09;一直迭代“最右”节点#xff0c;将其挂载到栈顶#xff08;“根”节点#x…栈
思路 思路与 力扣105. 从前序与中序遍历序列构造二叉树 相同差异的地方 从后序遍历数组尾部向前遍历根节点在尾部一直迭代“最右”节点将其挂载到栈顶“根”节点的右子树节点后序遍历从尾部迭代顺序变成了根-右子树-左子树出栈后挂载左子树
/*** 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(vectorint inorder, vectorint postorder) {if (!postorder.size()) {return nullptr;}int post_size postorder.size();std::stackTreeNode* stk;TreeNode* root new TreeNode(postorder[post_size - 1]);stk.push(root);int in_idx post_size - 1;for (int idx post_size - 2; idx 0; --idx) {TreeNode *node stk.top();int post_val postorder[idx];if (node-val ! inorder[in_idx]) {node-right new TreeNode(post_val);stk.push(node-right);} else {while (!stk.empty() (stk.top()-val inorder[in_idx])) {node stk.top();stk.pop();--in_idx;}node-left new TreeNode(post_val);stk.push(node-left);}}return root;}
};
