二叉树

深度优先遍历（DFS）

• 先序遍历：当前节点，左节点，右节点中，先检查当前节点，再左节点，最后右节点
• 中序遍历：当前节点，左节点，右节点中，先检查左节点，再当前节点，最后右节点
  • 二叉搜索树
    • 节点的左子树的值都小于节点
    • 节点的右子树的值都大于节点
    • 当二叉树是二叉搜索树时，中序遍历的值是从小到大的；
• 后序遍历：当前节点，左节点，右节点中，先检查左节点，再右节点，最后当前节点

先中后，指的是当前节点，左节点，右节点中当前节点的遍历顺序；先序即先遍历当前节点，中序即先左节点然后才当前节点，后序即先左、右节点后当前节点

// 先序遍历
function dfs(node){
    if(node == null) return
    console.log(node.val)
    dfs(node.left)
    dfs(node.right)
}

// 后序遍历
function dfs(node){
    if(node == null) return
    dfs(node.left)
    dfs(node.right)
    console.log(node.val)
}

迭代方法——深度遍历

function dfs(node){
    let stack = [node]
    while(stack.length !== 0){
        let curr = stack.pop()
        if(curr.left){
        	stack.push(curr.left)
        }else if(curr.right){
        	stack.push(curr.right)
        }else{
        	console.log(stack.pop())
        }
    }
    
}

广度优先遍历（WFS）

• 利用一个队列（先进先出）确保每层按序遍历

function wfs(root) {
  let queue = [root];
  while (queue.length > 0) {
    let curNode = queue.shift();
    console.log(curNode.val);
    curNode.left && queue.push(curNode.left);
    curNode.right && queue.push(curNode.right);
  }
}

// test
let testTree = {
  val: 10,
  left: {
    val: 9,
    left: { val: 2 },
    right: { val: 1 },
  },
  right: {
    val: 8,
    left: { val: 52 },
    right: { val: 14 },
  },
};
wfs(testTree);

• 分层的广度遍历

  var levelOrder = function(root) {
      const ret = [];
      if (!root) {
          return ret;
      }
  
      const q = [];
      q.push(root);
      while (q.length !== 0) {
          const currentLevelSize = q.length;
          ret.push([]);
          for (let i = 1; i <= currentLevelSize; ++i) {
              const node = q.shift();
              ret[ret.length - 1].push(node.val);
              if (node.left) q.push(node.left);
              if (node.right) q.push(node.right);
          }
      }
          
      return ret;
  };
  let testTree = {
    val: 10,
    left: {
      val: 9,
      left: { val: 2 },
      right: { val: 1 },
    },
    right: {
      val: 8,
      left: { val: 52 },
      right: { val: 14 },
    },
  };
  levelOrder(testTree);
  
  //作者：LeetCode-Solution
  //链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/
  //来源：力扣（LeetCode）
  //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最后更新： 2021年07月15日 23:40

原始链接： https://idkhts.github.io/2021/04/04/%E4%BA%8C%E5%8F%89%E6%A0%91/

idkhts