首页 > 代码库 > [LeetCode系列] 从中序遍历和后序遍历序列构造二叉树(迭代解法)
[LeetCode系列] 从中序遍历和后序遍历序列构造二叉树(迭代解法)
给定中序遍历inorder和后序遍历postorder, 请构造出二叉树.
算法思路: 设后序遍历为po, 中序遍历为io.
- 首先取出po的最后一个节点作为根节点, 同时将这个节点入stn栈;
- 随后比较io的最后一个节点和stn栈顶节点:
- 如果不同则将此节点添加到栈顶节点的右侧并入stn栈, 同时从po中删除这个节点;
- 此时的栈中保存了所有还未处理左子树的右侧根节点
- 出现一次不同, 右侧子树的深度就增加1, 栈的深度就代表了当前右侧子树的深度
- 如果相同, 先缓存栈顶节点, 分别删除io和栈顶元素:
- 如果依旧相同(说明本层没有左子树), 则返回第2步;
- 如果不同(说明有左子树), 则将po的最后一个节点添加到缓存节点p的左侧, 同时将左子树入栈并从po中删除此节点, 返回第2步;
- 如果不同则将此节点添加到栈顶节点的右侧并入stn栈, 同时从po中删除这个节点;
代码:
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {13 if(inorder.size() == 0)return NULL;14 TreeNode *p;15 TreeNode *root;16 stack<TreeNode *> stn;17 18 root = new TreeNode(postorder.back()); 19 stn.push(root); 20 postorder.pop_back(); 21 22 while(true)23 {24 if(inorder.back() == stn.top()->val) 25 {26 p = stn.top();27 stn.pop(); 28 inorder.pop_back(); 29 if(inorder.size() == 0) break;30 if(stn.size() && inorder.back() == stn.top()->val)31 continue;32 p->left = new TreeNode(postorder.back()); 33 postorder.pop_back();34 stn.push(p->left);35 }36 else 37 {38 p = new TreeNode(postorder.back());39 postorder.pop_back();40 stn.top()->right = p; 41 stn.push(p); 42 }43 }44 return root;45 }46 };
[LeetCode系列] 从中序遍历和后序遍历序列构造二叉树(迭代解法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。