前序遍历、中序遍历、后序遍历

前序遍历

前序遍历可以说最符合大家阅读树结构的查询顺序，它满足根节点=>左子树=>右子树的顺序
image.png
如上图，遍历顺序为ABC。
image.png
遍历顺序为ABCEGHCFI。
先遍历根节点，然后判断有没有左子树，如果有的话就接着遍历，而左子树也可以有自己的左子树和右子树，所以我们可以用递归来做到遍历。

例题：给定一个二叉树，返回它的前序遍历。

输入[1, null, 2, 3] :::info 1
\
2
/
3 ::: 输出[1,2,3]

  1. let preOrderTraversal = function(root) {
  2. let res = [];
  3.   function traversal(root) {
  4.     if(root !== null) {
  5.       res.push(root.val);
  6.       if(root.left) {
  7.         traversal(root.left);
  8.       };
  9.       if(root.right) {
  10.         traversal(root.right);
  11.       };
  12.     };
  13.   };
  14.   traversal(root);
  15.   return res;
  16. }

中序遍历

中序遍历满足左子树=>根节点=>右子树的顺序进行查询。
image.png
当跑到根节点B时，先看看有没有左子树，所以先遍历了左子树A之后才是B，最后遍历右子树C，所以完整顺序为ABC。
image.png
从F开始，先看有没有左子树，于是跑到了B，注意此时并不是直接取B，由于B也有左子树，所以第一个遍历到的节点其实是A，而A没有其它分支了，所以紧接着遍历A的根节点B，然后跑到B的右子树D。
而D也有自己的左子树和右子树，所以D不能被立刻遍历，而是先遍历C，然后才是D，最后是E。
此时F节点的左子树遍历完成，此时顺序为ABCDEF。
再看右子树，由于G没有左子树，所以直接遍历G，然后跑到G的右子树I，但I有左子树，所以先取H，再取I。所以此二叉树的中序遍历顺序为ABCDEFGHI。

例题：给定一个二叉树，返回它的中序遍历。

输入[1, null, 2, 3] :::info 1
\
2
/
3 ::: 输出[1,2,3]

  1. let inOrderTraversal = function(root) {
  2.   let result = [];
  3.   function traversal(root) {
  4.     if(root !== null) {
  5.       if(root.left) {
  6.         traversal(root.left);
  7.       }
  8.       result.push(root.val);
  9.       if(root.right) {
  10.         traversal(root.right);
  11.       }
  12.     }
  13.   }
  14.   traversal(root);
  15.   return res;
  16. }

后序遍历

后续遍历满足左子树=>右子树=>根节点的顺序进行查询
image.png
从根节点C出发，先访问左子树A，紧接着右子树B，最后根节点C，所以顺序为ABC。
image.png
从根节点I出发，于是成功找到了左子树E，所以第一个遍历到了A，紧接着来到E的右子树D，但D也有自己的左右子树，所以第二个遍历的是B，紧接着是C，最后是根节点D，根节点E，到这里左子树遍历完成，ABCDE。
再来看右子树H，由于H有右子树G，所以H不能被遍历，G也有自己的左子树F，所以遍历到了F，G没右子树，于是F之后就是G，紧接着H，到这里I的右子树遍历完成，最后遍历根节点I。所以完整的顺序为：ABCDEFGHI。

例题：给定一个二叉树，返回它的后序遍历。

输入[1, null, 2, 3] :::info 1
\
2
/
3 ::: 输出[1,2,3]

  1. let postorderTraversal = function(root) {
  2.   let res = [];
  3.   function traversal(root) {
  4.     if(root !== null) {
  5.       if(root.left) {
  6.         traversal(root.left);
  7.       };
  8.       if(root.right) {
  9.         traversal(root.right);
  10.       };
  11.       res.push(root.val);
  12.     }
  13.   }
  14.   traversal(root);
  15.   return res;
  16. }

层序遍历

层序遍历满足从上到下，从左到右一层一层遍历的顺序
image.png
首先从根节点A开始，这是第一层，遍历完成往下一层推进，于是访问到了B和C，完整顺序为ABC。
image.png
完整顺序为ABCDEFGHI。

例题：给定一个二叉树，返回它的层序遍历。

输入[3, 9, 20, null, null, 15, 15] :::info 3
/ \
9 20
/ \
15 7 ::: 返回其层次遍历结果[
[3],
[9, 20],
[15, 7]
]

  1. let levelOrder = function(root) {
  2.   let res = [];
  3.   function traversal(root, depth) {
  4.     if(root !== null) {
  5.       if(!res[depth]) {
  6.         res[depth] = [];
  7.       };
  8.       res[depth].push(root.val);
  9.       if(root.left) {
  10.         traversal(root.left, depth + 1);
  11.       };
  12.       if(root.right) {
  13.         traversal(root.right, depth + 1);
  14.       };
  15.     };
  16.   };
  17.   traversal(root, 0);
  18.   return res;
  19. }

例题：给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子结点的最长路径上的节点树。（叶子结点是指没有子节点的节点）。
实例：给定二叉树[3,9,20, null,null,15,7] :::info 3
/ \
9 20
/ \
15 7 ::: 返回它的最大深度3。

  1. let maxDepth = function(root) {
  2.   let ans = 0;
  3.   if(root === null) return ans;
  4.   function traversal(root, depth) {
  5.     ans = Math.max(ans, deepth);
  6.     if(root.left) {
  7.       traversal(root.left, deepth + 1);
  8.     };
  9.     if(root.right) {
  10.       traversal(root.right, depth + 1);
  11.     };
  12.   };
  13.   traversal(root, 1);
  14.   return ans;
  15. }

深度优先、广度优先与前、中、后、层序遍历的关系

前序、中序与后序遍历均为深度优先，而层序遍历也就是所谓的广度优先了。
对比不难发现，深度优先更具钻研精神，只要子树还有子，就一直往下查找。而广度是将每一层节点遍历完成为止，才会进入下一层。
image.png