前序遍历

使用递归的方式，先遍历父节点，再遍历左节点，最后再遍历右节点

  1. /**
  2.  * 二叉树的前序遍历 
  3.  * @params {TreeNode} root
  4.  */
  5. function preOrder(root) {
  6.   if (!root) {
  7.       return 
  8.   }
  10.   console.log(root.val);
  11.     preOrder(root.left);
  12.   preOrder(root.right);
  13. }

中序遍历

使用递归的方式，先遍历左节点，再遍历父节点，最后再遍历右节点

  1. /**
  2.  * 二叉树的中序遍历 
  3.  * @params {TreeNode} root
  4.  */
  5. function inOrder(root) {
  6.   if (!root) {
  7.       return 
  8.   }
  10.     inOrder(root.left);
  11.   console.log(root.val);
  12.   inOrder(root.right);
  13. }

后序遍历

使用递归的方式，先遍历左节点，再遍历右节点，最后再遍历父节点

  1. /**
  2.  * 二叉树的后序遍历 
  3.  * @params {TreeNode} root
  4.  */
  5. function postOrder(root) {
  6.   if (!root) {
  7.       return 
  8.   }
  10.     postOrder(root.left);
  11.   postOrder(root.right);
  12.   console.log(root.val);
  13. }

Morris 遍历

Morris 是 O(1) 空间复杂度的二叉树遍历算法

Morris 中序遍历的一个重要步骤就是寻找当前节点的前驱节点，并且 Morris 中序遍历寻找下一个点始终是通过转移到 rightright 指针指向的位置来完成的。

  • 如果当前节点没有左子树，则遍历这个点，然后跳转到当前节点的右子树。
  • 如果当前节点有左子树，那么它的前驱节点一定在左子树上，我们可以在左子树上一直向右行走，找到当前点的前驱节点。
  • 如果前驱节点没有右子树，就将前驱节点的 rightright 指针指向当前节点。这一步是为了在遍历完前驱节点后能找到前驱节点的后继，也就是当前节点。
  • 如果前驱节点的右子树为当前节点，说明前驱节点已经被遍历过并被修改了 rightright 指针，这个时候我们重新将前驱的右孩子设置为空，遍历当前的点，然后跳转到当前节点的右子树。 ```javascript /**
    • 二叉树的 Morris 遍历
    • @params {TreeNode} root */ function morrisTravers() {

} ```