数据结构与算法-二叉树的遍历递归&&非递归

墨蓝 2023-01-13 15:58 196阅读 0赞

### 文章目录 ###

*  一、递归
 *   *  1.前序
     *  2.中序
     *  3.后序
 *  二、非递归
 *   *  1.前序
     *  2.后序
     *  3.中序
     *  4.层序遍历(BFS)

# 一、递归 #

## 1.前序 ##

根左右

// 所有遍历函数的入参都是树的根结点对象
    function preorder(root) {
        // 递归边界，root 为空
        if(!root) {
            return 
        }
         
        // 输出当前遍历的结点值
        console.log('当前遍历的结点值是：', root.val)  
        // 递归遍历左子树 
        preorder(root.left)  
        // 递归遍历右子树  
        preorder(root.right)
    }

## 2.中序 ##

左根右

// 所有遍历函数的入参都是树的根结点对象
    function inorder(root) {
        // 递归边界，root 为空
        if(!root) {
            return 
        }
         
        // 递归遍历左子树 
        inorder(root.left)  
        // 输出当前遍历的结点值
        console.log('当前遍历的结点值是：', root.val)  
        // 递归遍历右子树  
        inorder(root.right)
    }

## 3.后序 ##

左右根

function postorder(root) {
        // 递归边界，root 为空
        if(!root) {
            return 
        }
         
        // 递归遍历左子树 
        postorder(root.left)  
        // 递归遍历右子树  
        postorder(root.right)
        // 输出当前遍历的结点值
        console.log('当前遍历的结点值是：', root.val)  
    }

# 二、非递归 #

利用栈来实现

## 1.前序 ##

/**
     * @param {TreeNode} root
     * @return {number[]}
     */
    const preorderTraversal = function(root) {
      // 定义结果数组
      const res = []  
      // 处理边界条件
      if(!root) {
          return res
      }
      // 初始化栈结构
      const stack = [] 
      // 首先将根结点入栈
      stack.push(root)  
      // 若栈不为空，则重复出栈、入栈操作
      while(stack.length) {
          // 将栈顶结点记为当前结点
          const cur = stack.pop() 
          // 当前结点就是当前子树的根结点，把这个结点放在结果数组的尾部
          res.push(cur.val)
          // 若当前子树根结点有右孩子，则将右孩子入栈
          if(cur.right) {
              stack.push(cur.right)
          }
          // 若当前子树根结点有左孩子，则将左孩子入栈
          if(cur.left) {
              stack.push(cur.left)
          }
      }
      // 返回结果数组
      return res
    };

## 2.后序 ##

后序和前序差不多的，把顺序换一下

/**
     * @param {TreeNode} root
     * @return {number[]}
     */
    const postorderTraversal = function(root) {
      // 定义结果数组
      const res = []  
      // 处理边界条件
      if(!root) {
          return res
      }
      // 初始化栈结构
      const stack = [] 
      // 首先将根结点入栈
      stack.push(root)  
      // 若栈不为空，则重复出栈、入栈操作
      while(stack.length) {
          // 将栈顶结点记为当前结点
          const cur = stack.pop() 
          // 当前结点就是当前子树的根结点，把这个结点放在结果数组的头部
          res.unshift(cur.val)
          // 若当前子树根结点有左孩子，则将左孩子入栈
          if(cur.left) {
            stack.push(cur.left)
          }  
          // 若当前子树根结点有右孩子，则将右孩子入栈
          if(cur.right) {
            stack.push(cur.right)
          }
      }
      // 返回结果数组
      return res
    };

## 3.中序 ##

中序稍复杂一点

/**
     * @param {TreeNode} root
     * @return {number[]}
     */
    const inorderTraversal = function(root) {
      // 定义结果数组
      const res = []  
      // 初始化栈结构
      const stack = []   
      // 用一个 cur 结点充当游标
      let cur = root  
      // 当 cur 不为空、或者 stack 不为空时，重复以下逻辑
      while(cur || stack.length) {
          // 这个 while 的作用是把寻找最左叶子结点的过程中，途径的所有结点都记录下来 
          while(cur) {
              // 将途径的结点入栈
              stack.push(cur)  
              // 继续搜索当前结点的左孩子
              cur = cur.left  
          }
          // 取出栈顶元素
          cur = stack.pop()  
          // 将栈顶元素入栈
          res.push(cur.val)  
          // 尝试读取 cur 结点的右孩子
          cur = cur.right
      }
      // 返回结果数组
      return res
    };

## 4.层序遍历(BFS) ##

用队列

function BFS(root) {
        if(!root) return;
        let res = []
        let queue = [] // 初始化队列queue
        // 根结点首先入队
        queue.push(root)
        // 队列不为空，说明没有遍历完全
        while(queue.length) {
            const top = queue.shift()
            // 访问 top
            res.push(top.val)
            // 如果左子树存在，左子树入队
            if(top.left) {
                queue.push(top.left)
            }
            // 如果右子树存在，右子树入队
            if(top.right) {
                queue.push(top.right)
            }
        }
    }

[本文链接https://blog.csdn.net/qq\_39903567/article/details/115865536][https_blog.csdn.net_qq_39903567_article_details_115865536]

[https_blog.csdn.net_qq_39903567_article_details_115865536]: https://blog.csdn.net/qq_39903567/article/details/115865536