前序遍历

前序遍历: 根结点 -> 左子树 -> 右子树

递归法

  1. // 所有遍历函数的入参都是树的根结点对象
  2. function preorder(root){
  3.   // 递归边界，root 为空
  4.   if(!root){
  5.     return;
  6.   }
  7.   // 输出当前遍历的结点值
  8.   console.log('当前遍历的结点值是：', root.val);
  9.   preorder(root.left);
  10.   preorder(root.right);
  11. }

迭代法

思路：

  • 将根结点入栈
  • 取出栈顶结点，将结点值 push 进结果数组
  • 若栈顶结点有右孩子，则将右孩子入栈
  • 若栈顶结点有左孩子，则将左孩子入栈
    1. /**
    2. * @param {TreeNode} root
    3. * @return {number[]}
    4. */
    5. const preorderTraversal = function(root) {
    6. // 定义结果数组
    7. const res = []  
    8. // 处理边界条件
    9. if(!root) {
    10.     return res
    11. }
    12. // 初始化栈结构
    13. const stack = [] 
    14. // 首先将根结点入栈
    15. stack.push(root)  
    16. // 若栈不为空，则重复出栈、入栈操作
    17. while(stack.length) {
    18.     // 将栈顶结点记为当前结点
    19.     const cur = stack.pop() 
    20.     // 当前结点就是当前子树的根结点，把这个结点放在结果数组的尾部
    21.     res.push(cur.val)
    22.     // 若当前子树根结点有右孩子，则将右孩子入栈 根左右 右离根远则先判断右边
    23.       cur.right && stack.push(cur.right)
    24.     // 若当前子树根结点有左孩子，则将左孩子入栈
    25.       cur.left && stack.push(cur.left)
    26. }
    27. // 返回结果数组
    28. return res
    29. };

    后序遍历

    递归法

    1. // 所有遍历函数的入参都是树的根结点对象
    2. function preorder(root){
    3. // 递归边界，root 为空
    4. if(!root){
    5.   return;
    6. }
    7. preorder(root.left);
    8. preorder(root.right);
    9. // 输出当前遍历的结点值
    10. console.log('当前遍历的结点值是：', root.val);
    11. }

    迭代法

    后序遍历的出栈序列，按照规则应该是 左 -> 右 -> 根 。这个顺序相对于先序遍历，最明显的变化就是根结点的位置从第一个变成了倒数第一个。
    和先序遍历二叉树类似，唯一区别是向数组中unshift元素，先push左再push右
    1. /**
    2. * @param {TreeNode} root
    3. * @return {number[]}
    4. */
    5. const preorderTraversal = function(root) {
    6. // 定义结果数组
    7. const res = []  
    8. // 处理边界条件
    9. if(!root) {
    10.     return res
    11. }
    12. // 初始化栈结构
    13. const stack = [] 
    14. // 首先将根结点入栈
    15. stack.push(root)  
    16. // 若栈不为空，则重复出栈、入栈操作
    17. while(stack.length) {
    18.     // 将栈顶结点记为当前结点
    19.     const cur = stack.pop() 
    20.     // 当前结点就是当前子树的根结点，把这个结点放在结果数组的尾部
    21.     res.unshift(cur.val)
    22.     // 若当前子树根结点有左孩子，则将左孩子入栈 左右根 左离根远则先判断左边
    23.       cur.left && stack.push(cur.left)
    24.     // 若当前子树根结点有右孩子，则将右孩子入栈
    25.       cur.right && stack.push(cur.right)
    26. }
    27. // 返回结果数组
    28. return res
    29. };

    中序遍历

    递归法

    1. // 所有遍历函数的入参都是树的根结点对象
    2. function preorder(root){
    3. // 递归边界，root 为空
    4. if(!root){
    5.   return;
    6. }
    7. preorder(root.left);
    8. // 输出当前遍历的结点值
    9. console.log('当前遍历的结点值是：', root.val);
    10. preorder(root.right);
    11. }

    迭代法

    1. /**
    2. * @param {TreeNode} root
    3. * @return {number[]}
    4. */
    5. const inorderTraversal = function(root) {
    6. // 定义结果数组
    7. const res = []  
    8. // 初始化栈结构
    9. const stack = []   
    10. // 用一个 cur 结点充当游标
    11. let cur = root  
    12. // 当 cur 不为空、或者 stack 不为空时，重复以下逻辑
    13. while(cur || stack.length) {
    14.     // 这个 while 的作用是把寻找最左叶子结点的过程中，途径的所有结点都记录下来 
    15.     while(cur) {
    16.         // 将途径的结点入栈
    17.         stack.push(cur)  
    18.         // 继续搜索当前结点的左孩子
    19.         cur = cur.left  
    20.     }
    21.     // 取出栈顶元素
    22.     cur = stack.pop()  
    23.     // 将栈顶元素入栈
    24.     res.push(cur.val)  
    25.     // 尝试读取 cur 结点的右孩子
    26.     cur = cur.right
    27. }
    28. // 返回结果数组
    29. return res
    30. };
  1. 两个 while ：内层的 while 的作用是在寻找最左叶子结点的过程中，把途径的所有结点都记录到 stack 里。记录工作完成后，才会走到外层 while 的剩余逻辑里——这部分逻辑的作用是从最左的叶子结点开始，一层层回溯遍历左孩子的父结点和右侧兄弟结点，进而完成整个中序遍历任务。
  2. 外层while 的两个条件：cur 的存在性和stack.length 的存在性，各自是为了限制什么？
    1. stack.length 的存在性比较好理解， stack 中存储的是没有被推入结果数组 res 的待遍历元素。只要 stack 不为空，就意味着遍历没有结束， 遍历动作需要继续重复。
    2. cur 的存在性就比较有趣了。它对应以下几种情况：
      1. 初始态， cur 指向 root 结点，只要 root 不为空， cur 就不为空。此时判断了 cur 存在后，就会开始最左叶子结点的寻找之旅。这趟“一路向左”的旅途中， cur 始终指向当前遍历到的左孩子。
      2. 第一波内层 while 循环结束， cur 开始承担中序遍历的遍历游标职责。 cur 始终会指向当前栈的栈顶元素，也就是“一路向左”过程中途径的某个左孩子，然后将这个左孩子作为中序遍历的第一个结果元素纳入结果数组。假如这个左孩子是一个叶子结点，那么尝试取其右孩子时就只能取到 null ，这个 null 的存在，会导致内层循环 while 被跳过，接着就直接回溯到了这个左孩子的父结点，符合 左->根 的序列规则
      3. 假如当前取到的栈顶元素不是叶子结点，同时有一个右孩子，那么尝试取其右孩子时就会取到一个存在的结点。 cur 存在，于是进入内层 while 循环，重复“一路向左”的操作，去寻找这个右孩子对应的子树里最靠左的结点，然后去重复刚刚这个或回溯、或“一路向左”的过程。如果这个右孩子对应的子树里没有左孩子，那么跳出内层 while 循环之后，紧接着被纳入 res 结果数组的就是这个右孩子本身，符合 根->右 的序列规则