二叉树非递归遍历实现

后序遍历;

  1. 将根节点的全部左子树入栈。
  2. 取栈顶元素,如果其右子树为空或者上次已经访问,则弹出。(因为左子树全部入栈只需要考虑右子树)
  3. 如果右子树 不为空,则入栈重复1。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    vector<int> postorderTraversal(TreeNode *root) {
    stack<TreeNode*> s;
    vector<int> v;
    TreeNode *p;
    TreeNode *r = NULL;//上次访问的结点
    p = root;
    if(!root) return v;
    while(p||!s.empty()){
    while(p){
    s.push(p);
    p = p->left;
    }
    p = s.top();
    if(!p->right||p->right == r){
    s.pop();
    r = p;
    v.push_back(p->val);
    p = NULL;
    }else{
    p = p->right;
    }
    }
    return v;
    }

前序遍历:
思路:

  1. 入栈根节点
  2. 弹出栈顶元素,如果根节点的右结点存在,则先放入右结点,如果根节点的左结点存在,再放入左结点
  3. 重复2,直到栈为空
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    vector<int> preorderTraversal(TreeNode *root){
    stack<TreeNode*> s;
    vector<int> v;
    TreeNode *t;
    s.push(root);
    if(!=root) return v;
    while(!s.empty()){
    t = s.top();
    s.pop();
    v.push_back(t);
    if(t->right) s.push(t->right);
    if(t->left ) s.push(t->left);
    }
    return v;
    }

中序遍历:
思路:

  1. 将当前结点(开始为根节点)左结点全部入栈
  2. 弹出栈顶元素,如果栈顶元素的右结点存在,则执行1(此时当前结点为右节点)。不存在则执行2.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    vector<int> orderTraversal(TreeNode * root){
    stack<TreeNode*> s;
    vector<int> v;
    TreeNode *p;
    p = root;
    while(p||!s.empty()){
    while(p){
    s.push(p);
    p = p->left;
    }
    p = s.top();
    v.push(p->val);
    s.pop();
    if(p->right)
    p = p->right;
    p = NULL;
    }
    return v;
    }
-------------本文结束感谢您的阅读-------------
鼓励鼓励!