二叉树的遍历

遍历分类

二叉树的遍历分类

  • 广度遍历
  • 深度遍历

深度遍历

深度遍历需要掌握递归算法和迭代算法两种

深度遍历分类

  • 前序遍历
    • 递归
    • 迭代
  • 中序遍历
    • 递归
    • 迭代
  • 后序遍历
    • 递归
    • 迭代

模板

递归

  1. // 递归法
  2. var traversal = function(root) {
  3.  let res=[];
  4.  const dfs=function(root){
  5.      if(root===null)return ;
  6.       // 根据前中后序变化位置 --- start
  8.                  //先序遍历所以从父节点开始
  9.           res.push(root.val);
  10.           //递归左子树
  11.         dfs(root.left);
  12.         //递归右子树
  13.         dfs(root.right);
  15.       // 根据前中后序变化位置 --- end
  16.  }
  17.  //只使用一个参数 使用闭包进行存储结果
  18.  dfs(root);
  19.  return res;
  20. };

迭代

因为是迭代，值的进栈顺序要反转一下

遍历顺序 出栈顺序 压栈顺序
前序遍历 中左右 右左中
中序遍历 左中右 右中左
后续遍历 左右中 中右左 
  1. var traversal = function(root, res = []) {
  2.     const stack = [];
  3.     if (root) stack.push(root);
  4.     while(stack.length) {
  5.         const node = stack.pop();
  6.         if(!node) {
  7.             res.push(stack.pop().val);
  8.             continue;
  9.         }
  10.           // 根据前中后序变化位置 --- start
  12.         if (node.right) stack.push(node.right); // 右
  13.         stack.push(node); // 中
  14.         stack.push(null);
  15.         if (node.left) stack.push(node.left); // 左
  17.         // 根据前中后序变化位置 --- end
  18.     };
  19.     return res;
  20. };

前序遍历

递归

  1. // 递归法
  2. var preorderTraversal = function(root) {
  3.  let res=[];
  4.  const dfs=function(root){
  5.      if(root===null)return ;
  6.      //先序遍历所以从父节点开始
  7.      res.push(root.val);
  8.      //递归左子树
  9.      dfs(root.left);
  10.      //递归右子树
  11.      dfs(root.right);
  12.  }
  13.  //只使用一个参数 使用闭包进行存储结果
  14.  dfs(root);
  15.  return res;
  16. };

迭代

  1. // 入栈 右 -> 左
  2. // 出栈 中 -> 左 -> 右
  3. var preorderTraversal = function(root, res = []) {
  4.     if(!root) return res;
  5.     const stack = [root];
  6.     let cur = null;
  7.     while(stack.length) {
  8.         cur = stack.pop();
  9.         res.push(cur.val);
  10.         cur.right && stack.push(cur.right);
  11.         cur.left && stack.push(cur.left);
  12.     }
  13.     return res;
  14. };

迭代法 - 统一法

  1. // 前序遍历：中左右
  2. // 压栈顺序：右左中
  4. var preorderTraversal = function(root, res = []) {
  5.     const stack = [];
  6.     if (root) stack.push(root);
  7.     while(stack.length) {
  8.         const node = stack.pop();
  9.         if(!node) {
  10.             res.push(stack.pop().val);
  11.             continue;                                                                              
  12.         }
  13.         if (node.right) stack.push(node.right); // 右
  14.         if (node.left) stack.push(node.left); // 左
  15.         stack.push(node); // 中
  16.         stack.push(null);
  17.     };
  18.     return res;
  19. };

中序遍历

递归

  1. // 递归法
  2. var postorderTraversal = function(root) {
  3.     let res=[];
  4.     const dfs=function(root){
  5.         if(root===null){
  6.             return ;
  7.         }
  8.         dfs(root.left);
  9.         dfs(root.right);
  10.         res.push(root.val);
  11.     }
  12.     dfs(root);
  13.     return res;
  14. };

迭代

// 入栈 左 -> 右
// 出栈 左 -> 中 -> 右

var inorderTraversal = function(root, res = []) {
    const stack = [];
    let cur = root;
    while(stack.length || cur) {
        if(cur) {
            stack.push(cur);
            // 左
            cur = cur.left;
        } else {
            // --> 弹出 中
            cur = stack.pop();
            res.push(cur.val); 
            // 右
            cur = cur.right;
        }
    };
    return res;
};

迭代法 - 统一法

//  中序遍历：左中右
//  压栈顺序：右中左

var inorderTraversal = function(root, res = []) {
    const stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const node = stack.pop();
        if(!node) {
            res.push(stack.pop().val);
            continue;
        }
        if (node.right) stack.push(node.right); // 右
        stack.push(node); // 中
        stack.push(null);
        if (node.left) stack.push(node.left); // 左
    };
    return res;
};

后序遍历

递归

// 递归法
var postorderTraversal = function(root) {
    let res=[];
    const dfs=function(root){
        if(root===null){
            return ;
        }
        dfs(root.left);
        dfs(root.right);
        res.push(root.val);
    }
    dfs(root);
    return res;
};

迭代

// 入栈 左 -> 右
// 出栈 中 -> 右 -> 左 结果翻转

var postorderTraversal = function(root, res = []) {
    if (!root) return res;
    const stack = [root];
    let cur = null;
    do {
        cur = stack.pop();
        res.push(cur.val);
        cur.left && stack.push(cur.left);
        cur.right && stack.push(cur.right);
    } while(stack.length);
    return res.reverse();
};

迭代法 - 统一法

// 后续遍历：左右中
// 压栈顺序：中右左

var postorderTraversal = function(root, res = []) {
    const stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const node = stack.pop();
        if(!node) {
            res.push(stack.pop().val);
            continue;
        }
        stack.push(node); // 中
        stack.push(null);
        if (node.right) stack.push(node.right); // 右
        if (node.left) stack.push(node.left); // 左
    };
    return res;
};

广度遍历

模板

var levelOrder = function (root) {
    //二叉树的层序遍历
    let res = [],
        queue = [];
    queue.push(root);
    if (root === null) {
        return res;
    }
    while (queue.length !== 0) {
        // 记录当前层级节点数
        let length = queue.length;
        //存放每一层的节点 
        let curLevel = [];
        for (let i = 0; i < length; i++) {
            let node = queue.shift();
            curLevel.push(node.val);
            // 存放当前层下一层的节点
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        //把每一层的结果放到结果数组
        res.push(curLevel);
    }
    return res;
};