如何使用网站营销,谷歌play商店,国外seo查询,企业网站建设公司网络二叉树的非递归遍历
先序
方法一:
先保存根节点#xff0c;用来之后找到右子树(利用栈来回溯到根#xff0c;进而找到右子树)
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint res; //存遍历序列stackTreeNode*…二叉树的非递归遍历
先序
方法一:
先保存根节点用来之后找到右子树(利用栈来回溯到根进而找到右子树)
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint res; //存遍历序列stackTreeNode* stk;TreeNode* p root;while(p || !stk.empty()){if(p ! nullptr){ res.push_back(p-val); //访问根节点stk.push(p);p p-left; //移动到左子树}else{ //如果左子树为空就需要访问上一个结点的右子树p stk.top();stk.pop();p p-right;}}return res;}
};
方法二:
不用回溯利用栈的先进后出性质先将右子树入栈再将左子树入栈实现根左右。
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {if(!root) return {};vectorint res; //存遍历序列stackTreeNode* stk;stk.push(root);while(!stk.empty()){TreeNode* p stk.top();stk.pop();res.push_back(p-val); //根if(p-right) stk.push(p-right); //将非空的右孩子压栈if(p-left) stk.push(p-left); //将非空的左孩子压栈}return res;}
};
方法三:统一迭代法
每次以根节点为处理对象如果当前遍历的结点非空则按照右左根顺序将三个结点都压入栈中在压入根节点之后继续压入空指针因此处理顺序与出栈顺序对应。如果为空则当前该结点需要输出。
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint res; //存遍历序列if(!root) return res;stackTreeNode* stk;stk.push(root);while(!stk.empty()){TreeNode* p stk.top();if(p ! nullptr){stk.pop();if(p-right) stk.push(p-right); //右if(p-left) stk.push(p-left); //左stk.push(p); //中stk.push(nullptr); //标记在空结点之下即为要处理的结点}else{stk.pop(); //弹出空结点p stk.top(); //访问要处理的结点stk.pop(); //弹出已处理好的结点res.push_back(p-val);}}return res;}
};
中序
方法一 与先序方法一类似将访问结点操作放在遍历到当前最左结点之后。
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint res; //存遍历序列stackTreeNode* stk;TreeNode* p root;while(p || !stk.empty()){if(p ! nullptr){ stk.push(p);p p-left; //移动到左子树}else{ //如果左子树为空就需要访问上一个结点的右子树p stk.top();stk.pop();res.push_back(p-val); //访问左p p-right;}}return res;}
};
方法二:统一迭代法
只需将先序中的统一迭代法按照右根左入栈即可。
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint res; //存遍历序列if(!root) return res;stackTreeNode* stk;stk.push(root);while(!stk.empty()){TreeNode* p stk.top();if(p ! nullptr){stk.pop();if(p-right) stk.push(p-right); //右stk.push(p); //中stk.push(nullptr); //标记在空结点之下即为要处理的结点if(p-left) stk.push(p-left); //左}else{stk.pop(); //弹出空结点p stk.top(); //访问要处理的结点stk.pop(); //弹出已处理好的结点res.push_back(p-val);}}return res;}
};
后序
方法一
改写先序方法一由于遍历顺序要求是左右根因此回溯的情况既可能是遍历完左子树也可能是遍历完右子树。如果是遍历完左子树且有右子树且右子树未被遍历过则需要继续遍历右子树如果是遍历完右子树则此时栈顶元素即为当前最右需要进行处理处理完最右结点需要回溯到根因此需要将当前指针置为空在下一次循环就可以取出栈顶根。由上可知需要标记结点是否被遍历过因此需要一个指针r记录上一个遍历过的结点。
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint res; //存遍历序列stackTreeNode* stk;TreeNode* p root;TreeNode* r nullptr;while(p || !stk.empty()){if(p ! nullptr){ stk.push(p);p p-left; //移动到左子树}else{ //如果左子树为空就需要检查右子树状态p stk.top();if(p-right r ! p-right){ //如果有右子树且未被遍历过p p-right;}else{ //否则应该处理栈顶元素p stk.top();stk.pop();res.push_back(p-val); //处理栈顶r p; //标记此结点已被处理p nullptr;}}}return res;}
};
方法二:改写先序方法二反转
先序方法二颠倒左右子树入栈顺序实现根右左再进行反转变成左右根。
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {if(!root) return {};vectorint res; //存遍历序列stackTreeNode* stk;stk.push(root);while(!stk.empty()){TreeNode* p stk.top();stk.pop();res.push_back(p-val); //根if(p-left) stk.push(p-left); //将非空的左孩子压栈if(p-right) stk.push(p-right); //将非空的右孩子压栈}reverse(res.begin(), res.end()); //反转数组return res;}
};
方法三:统一迭代法
按照根右左顺序入栈
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint res; //存遍历序列if(!root) return res;stackTreeNode* stk;stk.push(root);while(!stk.empty()){TreeNode* p stk.top();if(p ! nullptr){stk.pop();stk.push(p); //中stk.push(nullptr); //标记在空结点之下即为要处理的结点if(p-right) stk.push(p-right); //右if(p-left) stk.push(p-left); //左}else{stk.pop(); //弹出空结点p stk.top(); //访问要处理的结点stk.pop(); //弹出已处理好的结点res.push_back(p-val);}}return res;}
};
