关于面试问题:一文弄懂二叉树三种遍历方式

39次阅读

共计 3966 个字符，预计需要花费 10 分钟才能阅读完成。

关注公众号: 高性能架构摸索。后盾回复【材料】，能够收费支付

俗话说：学如逆水行舟, 逆水行舟; 心似平原走马, 易放难收。这句话对程序员而言，领会更深。这行曾经越来越卷了，时刻筹备着，😃。
二叉树，在面试中，已是必备的开胃菜。而在二叉树相干的面试题目中，遍历更是常考题目。本文将从二叉树的遍历角度动手，从递归和非递归角度来剖析和解说二叉树的遍历。

遍历

二叉树的遍历是指从根节点登程，依照某种秩序顺次拜访二叉树中的所有节点，使每个节点被且仅被拜访一次。

二叉树的遍历，有 先序遍历 、 中序遍历 以及 后续遍历 三种。

下面三种遍历形式中的先序、中序以及后序三种形式，是父节点绝对于子节点来说的。如果父节点先于子节点，那么就是先序遍历。如果子节点先于父节点，那么就是后序遍历。而对于子节点来说，如果先左节点，而后是父节点，而后再是右节点，那么就是中序遍历。

如【图一】所示二叉树。其三种遍历后果如下：

先序遍历: A->B->D->E->C->F->G

中序遍历: D->B->E->A->F->C->G

后续遍历: D->E->B->F->G->C->A

为了便于了解代码，咱们先定义下树的节点定义：

struct TreeNode {
  TreeNode *left;
  TreeNode *right;
  int val;
};

先序遍历

定义：先拜访父节点，而后遍历左子树，最初遍历右子树。

递归

置信递归遍历大家都会很容易写进去，且 bugfree。因为实现代码很简略。

在上图【图二】中，应用递归遍历，就是将其左子树和右子树也当做一棵树来进行解决。代码如下：

void PreOrder(TreeNode *root) {if (!root) {return;}
   
   // 遍历根节点(此处仅为输入，读者也能够依据理论须要进行解决，比方存储等)
   std::cout << root->val << std::endl;
   
   // 遍历左子树
   PreOrder(root->left);
   
   // 遍历右子树
   PreOrder(root->right);
}

非递归

在非递归操作中，咱们依然是依照先拜访根节点，而后遍历左子树，接着遍历右子树的形式。

  1. 达到节点 A, 拜访节点 A, 开始遍历 A 的左子树
  2. 达到节点 B，拜访节点 B，开始遍历 B 的左子树

  3. 达到节点 D, 拜访节点 D, 因为节点 D 无子树，因而节点 D 遍历实现

    • 节点 D 遍历实现，意味着节点 B 的左子树遍历实现，因而接着遍历节点 B 的右子树

  4. 达到节点 E，拜访节点 E。因为节点 E 无子树，因而节点 E 遍历实现

    • 节点 E 遍历实现，意味着节点 B 的右子树遍历实现，也预示着节点 B 的子树遍历实现
    • 开始遍历节点 A 的右子树
  5. 达到节点 C，拜访节点 C。开始遍历 C 的左子树

  6. 达到节点 F，拜访节点 F。因为节点 F 无子树，因而节点 F 遍历实现

    • 节点 F 遍历实现，意味着节点 C 的左子树遍历实现，因而开始遍历节点 C 的右子树

  7. 到的节点 G，拜访节点 G。因为节点 G 无子树，因而节点 G 遍历实现

    • 节点 G 遍历实现，意味着节点 C 的右子树遍历实现，进而预示着节点 C 遍历实现
    • 节点 C 遍历实现，意味着节点 A 的右子树遍历实现，进而意味着节点 A 遍历实现，因而以 A 为根节点的树遍历实现。

用非递归形式遍历二叉树，须要引入额定的数据结构栈(stack), 其根本流程如下：
1、申请一个栈 stack，而后将头节点压入 stack 中。

2、从 stack 中弹出栈顶节点，打印

3、将其右孩子节点（不为空的话）先压入 stack 中

4、将其左孩子节点（不为空的话）压入 stack 中。

5、一直反复步骤 2、3、4，直到 stack 为空，全副过程完结。

代码如下：

void PreOrder(TreeNode *root) {if (!root) {return;}
  
  std::stack<TreeNode*> s;
  s.push(root); // 步骤 1
  
  while (!s.empty()) {auto t = s.top();
    s.pop();// 出栈
    
    std::cout << t->val << std::endl; // 拜访节点
    if (t->right) {s.push(t->right); // 对应步骤 3
    }
    
    if (t->left) {s.push(t->left); // 对应步骤 4
    }
  }
}

中序遍历

定义：先遍历左子树，拜访根节点，遍历右子树

递归

在上图【图四】中，应用递归遍历，就是将其左子树和右子树也当做一棵树来进行解决。代码如下：

void InOrder(TreeNode *root) {if (!root) {return;}
   
  
   
   // 遍历左子树
   InOrder(root->left);
   
    // 遍历根节点(此处仅为输入，读者也能够依据理论须要进行解决，比方存储等)
   std::cout << root->val << std::endl;
   
   // 遍历右子树
   InOrder(root->right);
}

上述中序遍历的递归代码，相比于先序遍历，只是将拜访根节点的行为放在了遍历左右子树之间。

非递归

在非递归操作中，咱们依然是依照先遍历左子树，而后拜访根节点，最初遍历右子树的形式。

  1. 达到节点 A，节点 A 有左子树，遍历节点 A 的左子树
  2. 达到节点 B，节点 B 有左子树，遍历节点 B 的左子树

  3. 达到节点 D，节点 D 无子树，拜访 D 节点

    • 因为 D 无子树，意味着 B 的左子树遍历实现，那么就回到 B 节点
  4. 拜访 B 节点，遍历 B 节点的右子树

  5. 达到节点 E，节点 E 无子树，拜访节点 E

    • E 节点遍历实现，意味着以 B 为根的子树遍历实现，回到 A 节点
  6. 达到 A 节点，拜访 A 节点，遍历 A 节点的右子树
  7. 达到 C 节点，遍历 C 节点的左子树

  8. 达到 F 节点，因为 F 节点无子树，因而拜访 F 节点。

    • 因为 F 节点无子树，意味着 C 节点的左子树遍历实现，回到 C 节点
  9. 达到 C 节点，拜访 C 节点，遍历 C 的右子树

  10. 达到节点 G，因为 G 无子树，因为拜访节点 G

    • G 节点遍历实现，意味着 C 节点的右子树遍历实现，进而意味着 A 节点的右子树遍历实现，从意味着以 A 节点为根的二叉树遍历实现。

中序遍历，同样须要额定的辅助数据结构栈。

  1. 将根节点放入栈
    2、如果根节点有左子树，则将左子树的根节点放入栈
    3、反复步骤 1 和 2. 持续遍历左子树
    4、从栈中弹出节点，进行拜访，而后遍历右子树(反复步骤 1 和 2)
    5、如果栈为空，则遍历实现

代码如下：

void InOrder(TreeNode *root) {if (!root) {return;}
  
  std::stack<TreeNode*> s;
  auto p = root;
  
  while (!s.empty() || p) {if (p) { // 步骤 1 和 2
      s.push(p);
      p = p->left;
    } else { // 步骤 4
      auto t = s.top();
      std::cout << t->val << std::endl;
      p = t->right;
    }
  }
}

后续遍历

定义：先遍历左子树，再遍历右子树，最初拜访根节点

递归

void PostOrder(TreeNode *root) {if (!root) {return;}
   
   // 遍历左子树
   PostOrder(root->left);
   
   // 遍历右子树
   PostOrder(root->right);
   
    // 遍历根节点(此处仅为输入，读者也能够依据理论须要进行解决，比方存储等)
   std::cout << root->val << std::endl;
}

下面就是后续遍历的递归写法，比拟写先序遍历、中序遍历以及后续遍历三者的递归遍历写法，大部分代码是一样的，惟一的区别就是 拜访根节点的代码地位 不一样：

先序遍历：先拜访根节点，而后遍历左子树，最初遍历右子树
中序遍历：先遍历左子树，而后拜访根节点，最初遍历右子树
后序遍历：先遍历左子树，而后遍历右子树，最初拜访根节点

非递归

在非递归操作中，咱们依然是依照先遍历左子树，而后拜访根节点，最初遍历右子树的形式。

  1. 达到节点 A，遍历 A 的左子树
  2. 达到节点 B，遍历 B 的左子树

  3. 达到节点 D，因为 D 无子树，则拜访节点 D

    • 节点 D 无子树，意味着节点 B 的左子树遍历实现，接着遍历 B 的右子树

  4. 达到节点 E，因为 E 无子树，则拜访节点 E

    • 节点 E 无子树，意味着节点 B 的右子树遍历实现，接回到节点 B
  5. 拜访节点 B，回到节点 B 的根节点 A
  6. 达到节点 A，拜访节点 A 的右子树
  7. 达到节点 C，遍历节点 C 的左子树

  8. 达到节点 F，因为节点 F 无子树，因而拜访节点 F

    • 节点 F 拜访实现，意味着 C 节点的左子树遍历实现，因而回到节点 C
  9. 达到节点 C，遍历节点 C 的右子树

  10. 达到节点 G，因为节点 G 无子树，因为拜访节点 G

    • 节点 G 拜访实现，意味着 C 节点的右子树遍历实现，回到节点 C

  11. 达到节点 C，拜访节点 C

    • 节点 C 遍历实现，意味着节点 A 的右子树遍历实现，回到节点 A
  12. 节点 A 的右子树遍历实现，拜访节点 A

用非递归形式遍历二叉树，须要引入额定的数据结构栈(stack), 其根本流程如下：
1、申请两个栈 stack，而后将头节点压入指定 stack 中。

2、从 stack 中弹出栈顶节点，放入另外一个栈中

3、将其左孩子节点（不为空的话）先压入 stack 中

4、将其右孩子节点（不为空的话）压入 stack 中。

5、一直反复步骤 2、3、4，直到 stack 为空。

6、反复拜访另外一个栈，直至栈空

void PostOrder(TreeNode *root) {if (!root) {return;}
  
  std::stack<TreeNode*> s1;
  std::stack<TreeNode*> s2;
  
  s1.push(root);
  
  while (!s1.empty()) {auto t = s1.top();
    s1.pop();
    s2.push(t);
    
    if (t->left) {s1.push(t->left);
    }
    
    if (t->right) {s1.push(t->right);
    }
  }
  
  while (!s2.empty()) {auto t = s2.top();
    s2.pop();
    std::cout << t->val << std::endl;
  }
}

结语

对于二叉树来说，所谓的遍历，是指沿着某条路线顺次拜访每个节点，且均只做一次拜访。二叉树的遍历，是面试中常面算法之一，肯定要把其弄懂，必要的时候，须要背诵，乃至做到肌肉记忆。

正文完
面试问题
发表至： 面试问题
2021-08-31
 0
关于面试问题:微软M365-data团队面试复盘
关于面试问题:网络面试题集锦
关于面试问题:面试题JVM004-StringStringBuilderStringBuffer-有什么不同
关于面试问题:见招拆招老油条教你如何化解大厂面试官的线程池夺命连环炮