思路一

借鉴先序和中序遍历，两个辅助栈实现

  1. void bfs(TreeNode* root){
  2.     if (!root)return;
  3.     stack<TreeNode*> s1;
  4.     stack<TreeNode*> s2;
  5.     TreeNode *p = root;
  6.     while (!s1.empty() || p){
  7.         while (p){
  8.             s1.push(p);
  9.             s2.push(p);
  10.             p = p->right;
  11.         }
  12.         p = s1.top();
  13.         s1.pop();
  14.         p = p->left;
  15.     }
  16.     while (!s2.empty()){
  17.         cout << s2.top()->val << endl;//后序遍历
  18.         s2.pop();
  19.     }
  20. }

思路二

用一个额外结点存前一个结点，记录前一个结点和当前结点信息

  1. void bfs(TreeNode* root){
  2.     if (!root)return;
  3.     stack<TreeNode*> s;
  4.     TreeNode *cur = root, *pre = nullptr;
  5.     s.push(root);
  6.     while (!s.empty()){
  7.         cur = s.top();
  8.         if (!pre || pre->left == cur || pre->right == cur){//如果pre为空或pre是cur的父节点
  9.             if (cur->left)
  10.                 s.push(cur->left);
  11.             else if (cur->right)
  12.                 s.push(cur->right);
  13.         }
  14.         else if (cur->left == pre){//如果pre是cur的左孩子
  15.             if (cur->right)
  16.                 s.push(cur->right);
  17.         }
  18.         else{//如果pre和cur相同或pre是cur的右孩子
  19.             cout << cur->val << endl;
  20.             s.pop();
  21.         }
  22.         pre = cur;
  23.     }
  25. }