二叉树的遍历

前言

手写一下二叉树的遍历，主要有：

• 三种DFS深度优先遍历：前序遍历，中序遍历，后序遍历，其中这三种都包含递归和非递归（迭代）的两种写法。(3*2)

• 两种BFS广度优先遍历：层序遍历和锯齿形层序遍历（第一层从左到右第二层从右到左以此类推）。(2*1)

• 一种垂序遍历。(1*1)

DFS

前序遍历

前序遍历指的是对二叉树节点的操作时机遵循根节点-左节点-右节点的顺序。

题目地址：

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

前序遍历递归

没啥好说的。递归...

const preorderTraversal = function(root) {
  const result = [];
  dfs(root);
  function dfs(root) {
    if (!root) return;
    result.push(root.val);
    dfs(root.left);
    dfs(root.right);
  }
  return result;
};

前序遍历非递归

const preorderTraversal = root => {
  const result = [];
  if (!root) return result;
  const stack = [root];
  while (stack.length > 0) {
    let node = stack.pop();
    if (node) {
      result.push(node.val);
      stack.push(node.right);
      stack.push(node.left);
    }
  }
  return result;
};

中序遍历

中序遍历指的是对二叉树节点的操作时机遵循左节点-根节点-右节点的顺序。

题目地址：

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

中序遍历递归

const inorderTraversal = function(root) {
  const result = [];
  dfs(root);
  function dfs(root) {
    if (!root) return;
    dfs(root.left);
    result.push(root.val);
    dfs(root.right);
  }
  return result;
};

中序遍历非递归

const inorderTraversal = root => {
  const result = [];
  if (!root) return result;
  const stack = [];
  let node = root;
  while (stack.length > 0 || node) {
    if (node) {
      stack.push(node);
      node = node.left;
    } else {
      node = stack.pop();
      result.push(node.val);
      node = node.right;
    }
  }
  return result;
};

后序遍历

后序遍历指的是对二叉树节点的操作时机遵循左节点-右节点-根节点的顺序。

题目地址：

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

后序遍历递归

var postorderTraversal = function(root) {
  const result = [];
  dfs(root);
  function dfs(root) {
    if (!root) return;
    dfs(root.left);
    dfs(root.right);
    result.push(root.val);
  }
  return result;
};

后序遍历非递归

与中序遍历非递归主流程基本一致。最重要的不同是某个节点能不能立即访问的条件取决于右子树为空或者右子树已经访问过了。

var postorderTraversal = function(root) {
  const result = [];
  if (!root) return result;
  const stack = [];
  let node = root;
  let prev = null;
  while (stack.length > 0 || node) {
    if (node) {
      stack.push(node);
      node = node.left;
    } else {
      node = stack.pop();
      // 关键 节点访问条件 右子树为空 或者 右子树已经访问过了
      // 利用一个prev变量记录
      if (node.right == null || prev == node.right) {
        result.push(node.val);
        prev = node;
        node = null;
      } else {
        // 如果不能访问则当前节点重新入栈
        stack.push(node);
        node = node.right;
        prev = node;
      }
    }
  }
};

BFS

层序遍历

顾名思义，一层一层处理节点。

• 题目地址：

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

• 思路：借助队列先进先出（FIFO）的特点，进行模拟。

var levelorderTraversal = function (root) {
  const result = [];
  if (!root) return result;
  const queue = [root];
  while (queue.length > 0) {
    let node = queue.shift();
    if (node) {
      result.push(node.val);
      queue.push(node.left);
      queue.push(node.right);
    } else {
      // 空节点处理..
    }
  }
  return result;
};

• 变体，层序遍历分层返回一个二维数组。

• 题目地址：

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

• 思路：很多做法，无非就是在要记住操作节点的时候当前节点在哪一层，可以在入队的时候把层数入队，用作下一层叠加。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelorderTraversal = function(root) {
  const result = [];
  if (!root) return result;
  const queue = [{
    // 树节点
    cur: root,
    // 当前层数
    level: 0
  }];
  while (queue.length > 0) {
    let node = queue.shift();
    if (node.cur) {
      if (!result[node.level]) {
        // 初始化空数组
        result[node.level] = [];
      }
      result[node.level].push(node.cur.val);
      queue.push({
        cur: node.cur.left,
        level: node.level + 1
      });
      queue.push({
        cur: node.cur.right,
        level: node.level + 1
      });
    }
  }
  return result;
};

• 也可以不要额外的变量，队列不为空，循环处理完当层的节点推入一个数组。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelorderTraversal = function(root) {
  const result = [];
  if (!root) return result;
  const queue = [root];
  while (queue.length > 0) {
    let arr;
    let length = queue.length;
    // 循环处理当前层级
    while (length --) {
      let node = queue.shift();
      if (node) {
        if (!arr) arr = [];
        arr.push(node.val);
        queue.push(node.left);
        queue.push(node.right);
      }
    }
    // 最后一层可能都是空节点 所以这里做一下判断
    if (arr) result.push(arr);
  }
  return result;
};

锯齿形层序遍历

与层序遍历类似，只不过每处理一层会换个处理的方向，第一层从左向右，第二层从右向左，以此类推，像锯齿形状的遍历途径。

题目地址：

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
  const result = [];
  if (!root) return result;
  const queue = [root];
  let directionRight = true; // 初始化右方向 每一层换方向
  while (queue.length > 0) {
    let arr;
    let length = queue.length;
    // 循环处理当前层级
    while (length --) {
      let node = queue.shift();
      if (node) {
        if (!arr) arr = [];
        if (directionRight) { // 右方向从尾部开始插入元素
          arr.push(node.val);
        } else { // 左方向从头部开始插入元素
          arr.unshift(node.val);
        }
        queue.push(node.left);
        queue.push(node.right);
      }
    }
    // 最后一层可能都是空节点 所以这里做一下判断
    if (arr) {
      // 每加一层就换个方向
      directionRight = !directionRight;
      result.push(arr);
    }
  }
  return result;
};

垂序遍历

有点难描述，具体的看下题目描述。

题目地址：

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

思路：

• 前序遍历记录坐标值和节点值。
• 根据坐标值和节点值排序：优先级：列坐标 > 行坐标 > 节点值。
• 组装结果数据，将列坐标相同的放到同一个数组中，不同列坐标放不同数组，返回一个二维数组。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function (root) {
  if (!root) return [];
  const locationList = [];
  // 前序遍历记录坐标点
  dfs(root, 0, 0);
  // 排序
  locationList.sort((a, b) => {
    // 先根据列坐标排
    if (a[1] !== b[1]) return a[1] - b[1];
    // 再根据行坐标排
    if (a[0] !== b[0]) return a[0] - b[0];
    // 再根据值大小排
    return a[2] - b[2];
  });
  const length = locationList.length;
  const result = [[locationList[0][2]]];
  let prev = locationList[0][1];
  // 组装结果数据 循环 遇到列坐标不同就新push一个数组 相同就push到上一个数组的尾部
  for (let i = 1; i < length; i++) {
    if (locationList[i][1] !== prev) {
      result.push([locationList[i][2]]);
      prev = locationList[i][1];
    } else {
      result[result.length - 1].push(locationList[i][2]);
    }
  }
  return result;
  function dfs(root, x, y) {
    if (root) {
      locationList.push([x, y, root.val]);
      dfs(root.left, x + 1, y - 1);
      dfs(root.right, x + 1, y + 1);
    }
  }
};