前序遍历

递归

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) {
            return vector<int>();
        }
        
        stack<TreeNode*> S;
        vector<int> preOrder;
        TreeNode* p = root;
        
        while(!S.empty() || p) {
            while(p) {
                preOrder.emplace_back(p->val);
                S.emplace(p);
                p = p->left;
            }
            
            p = S.top();
            S.pop();
            p = p->right;
        }

        return preOrder;
    }
};

中序遍历

递归

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> inOrder;
        TreeNode* p = root;

        while(!stk.empty() || p) {
            while(p) {
                stk.emplace(p);
                p = p->left;
            }

            p = stk.top();
            stk.pop();
            inOrder.emplace_back(p->val);
            p = p->right;
        }

        return inOrder;
    }
};

后序遍历

递归

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// leetcode
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    vector<int> postOrder;
    TreeNode* prev = nullptr;

    while(!stk.empty() || root != nullptr) {
        // 向左至子树最左侧
        while(root != nullptr) {
            stk.emplace(root);
            root = root->left;
        }

        // 取子树最左侧的节点
        root = stk.top();
        // stk.pop();

        // 检查当前节点是否有右子树或右子树是否已访问
        if(root->right == nullptr || root->right == prev) {
            postOrder.emplace_back(root->val);
            prev = root;
            root = nullptr;
            stk.pop();    // 确定右子树已访问后，栈顶元素出栈
        } else {
            // stk.emplace(root);
            root = root->right;
        }
    }

    return postOrder;
}
---

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 左程云
void PostOrder( BiTree T)
{
  InitStack(S);
  p=T;
  r=NULL;
  while(p || !IsEmpty(S))
  {
    if (p){                                          //走到最左边
      push(S,p);
      p=p->lchild;
    }
    else
    {
      GetTop(S,p);                      //向右，取栈顶结点。
      if (p->rchild && p->rchild!=r)    //若右子树存在，且未被访问过
      {
        p = p->rchild;              //转向右
        push(S,p);                      //压栈
        p = p->lchild;              //再走到最左
      }
      else
      {                       //否则，弹出结点并访问
        pop(S,p);        //将结点弹出
        visit(p->data);        //访问该结点
        r = p;                   //记录最近访问过的结点
        p = NULL;            //结点访问完后，重置p指针
      }
    }
  }
}