二叉树遍历

二叉树的四种遍历方式

1. 先序遍历

1.1 递归实现

void preorder(Treenode *root) {
    if ( root == nullptr ) return;
    cout << root->val << ' ';
    preorder(root->left);
    preorder(root->right);
}

1.2 迭代实现

对于任何一个节点cur:

1. 访问cur, 并将cur入栈, 为了将来找到cur的右孩子
2. 如果cur的左孩子为空, 说明没有左孩子要处理, 出栈, 将cur指向栈顶的右孩子;
3. 如果cur的左孩子不为空, 说明有左孩子要处理, 直接将cur指向左孩子即可;

   void preorder(Treenode *root) {
       if ( root == nullptr ) return;
       stack<Treenode*> stk;
       Treenode *cur = root;
       while ( cur != nullptr || !stk.empty() ) {
           while ( cur != nullptr ) {
               cout << cur->val << ' ';
               stk.push(cur);
               cur = cur->left;
           }
           if ( !stk.empty() ) {
               cur = stk.top();
               stk.pop();
               cur = cur->right;
           }
       }
   }

2. 中序遍历

2.1 递归实现

void inorder(Treenode *root) {
    if ( root == nullptr ) return;
    inorder(root->left);
    cout << root->val << ' ';
    inorder(root->right);
}

2.2 迭代实现

对于任何一个节点cur:

1. 如果cur的左孩子不为空, 说明有左孩子需要处理, 将当前节点入栈;
2. 如果cur的左孩子为空, 说明没有左孩子需要处理了, 那么就可以处理栈顶的节点, 出栈处理访问, 然后将cur指向栈顶节点的右孩子

   void inorder(Treenode *root) {
       if ( root == nullptr ) return;
       stack<Treenode*> stk;
       Treenode* cur = root;
       while ( cur != nullptr || !stk.empty() ) {
           while ( cur != nullptr ) {
               stk.push(cur);
               cur = cur->left;
           }
           if ( !stk.empty() ) {
               cur = stk.top();
               stk.pop();
               cout << cur->val << ' ';
               cur = cur->right;
           }
       }
   }