晾衣架 东莞网站建设,咖啡网页怎么制作,网站建站方案说明书,河南响应式建站目录
6. 根据一棵树的前序遍历与中序遍历构造二叉树
题目
分析
代码
7. 根据一棵树的中序遍历与后序遍历构造二叉树
题目
分析
代码
8. 二叉树的前序遍历#xff0c;非递归迭代实现
题目
分析
代码
9. 二叉树中序遍历 #xff0c;非递归迭代实现
题目
分析
…目录
6. 根据一棵树的前序遍历与中序遍历构造二叉树
题目
分析
代码
7. 根据一棵树的中序遍历与后序遍历构造二叉树
题目
分析
代码
8. 二叉树的前序遍历非递归迭代实现
题目
分析
代码
9. 二叉树中序遍历 非递归迭代实现
题目
分析
代码
10. 二叉树的后序遍历 非递归迭代实现
题目
分析
代码 6. 根据一棵树的前序遍历与中序遍历构造二叉树
题目
OJ链接 分析
前序遍历的第一个结点一定是根节点根据根结点在中序结点的位置可以划分出根节点的左右结点范围然后根据递归调用不断地划分子树的左右结点代码如下
代码
class Solution {
public:TreeNode* createTree(vectorint preorder, vectorint inorder,int cur,int begin,int end){if (begin end)return nullptr;int root begin;//寻找根节点在中序遍历的位置while (root end){if (preorder[cur] inorder[root])break;root;}TreeNode* ret new TreeNode(preorder[cur]);ret-leftcreateTree(preorder, inorder, cur, begin, root-1);ret-rightcreateTree(preorder, inorder, cur, root1, end);return ret;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {if (preorder.empty() || inorder.empty())return nullptr;int cur0;int begin 0;int end inorder.size() - 1;return createTree(preorder, inorder,cur,begin,end);}
};
7. 根据一棵树的中序遍历与后序遍历构造二叉树
题目
OJ链接
分析
方法跟上一题类似只是后续遍历的根节点要从最后一位找并且向前遍历同时要注意先找右子树再找左子树。
代码
class Solution {
public:TreeNode* createTree(vectorint postorder, vectorint inorder, int cur, int begin, int end){if (begin end)return nullptr;int root begin;while (root end){if (postorder[cur] inorder[root])break;root;}TreeNode* ret new TreeNode(postorder[cur--]);ret-right createTree(postorder, inorder, cur, root 1, end);ret-left createTree(postorder, inorder, cur, begin, root - 1);return ret;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {if (postorder.empty() || inorder.empty())return nullptr;int cur inorder.size() - 1;int begin 0;int end cur;return createTree(postorder, inorder, cur, begin, end);}
};
8. 二叉树的前序遍历非递归迭代实现
题目
OJ链接
分析
任意一个树我们都可以分为两部分左路结点和左路结点的右子树如下图 左路结点的右子树又可以分为新的左路结点和左路结点的右子树
通过这种思路如下代码所示
代码
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint ans;if (root nullptr)return ans;TreeNode* cur root;stackTreeNode* st;while (!st.empty()||cur){//插入所有左路结点到栈中while (cur){st.push(cur);ans.push_back(cur-val);cur cur-left;}//对左路结点进行出栈并将左路结点的右子树的根作为新的cur结点//下一层循环访问右子树的所有左路结点插入到栈中TreeNode* top st.top();st.pop();cur top-right;}return ans;}
};
9. 二叉树中序遍历 非递归迭代实现
题目
OJ链接 分析
将上一题的ans.push_back放到下面既可以完成
代码
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint ans;if (root nullptr)return ans;TreeNode* cur root;stackTreeNode* st;while (!st.empty()||cur){while (cur){st.push(cur);cur cur-left;}TreeNode* top st.top();st.pop();ans.push_back(top-val);cur top-right;}return ans;}
};
10. 二叉树的后序遍历 非递归迭代实现
题目
OJ链接 分析
因为是后序遍历父亲结点最后插入所以要判断右结点是否为空或者右结点是上一次访问过的结点
代码
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint ans;if (root nullptr)return ans;TreeNode* prenode nullptr;TreeNode* cur root;stackTreeNode* st;while (!st.empty() || cur) {while (cur) {st.push(cur);cur cur-left;}TreeNode* top st.top();if (top-right nullptr || prenode top-right) {st.pop();ans.push_back(top-val);prenode top;} else {cur top-right;}}return ans;}
};
