二叉树遍历

根据二叉树前序遍历顺序创建的数组构建一个二叉树

function Node(data, left, right){
  this.data = data
  this.left = left
  this.right = right
}

var list = [3, 2, 9, null, null, 10, null, null, 8, null, 1]

function createBinaryTree(list){
  var node = null

  if(list.length === 0){
    return null
  }

  var data = list.shift()
  if(data !== null){
    node = new Node(data, createBinaryTree(list), createBinaryTree(list))
  }
  return node
}

console.log(createBinaryTree(list))

/*
Node {
  data: 3,
  left: Node {
    data: 2,
    left: Node {
      data: 9,
      left: null,
      right: null,
    },
    right: Node {
      data: 10,
      left: null,
      right: null,
    },
  },
  right: Node {
    data: 8,
    left: null,
    right: Node {
      data: 1,
      left: null,
      right: null,
    },
  },
}
*/

深度优先遍历

递归的思路

前序遍历

var treeNode = createBinaryTree(list)

function preOrderTraversal(node){
  if(node === null){
    return
  }

  console.log(node.data)
  preOrderTraversal(node.left)
  preOrderTraversal(node.right)
}

preOrderTraversal(treeNode)

// 3 2 9 10 8 1

中序遍历

function inOrderTraversal(node){
  if(node === null){
    return
  }

  inOrderTraversal(node.left)
  console.log(node.data)
  inOrderTraversal(node.right)
}

inOrderTraversal(treeNode)

// 9 2 10 3 8 1

后序遍历

function postOrderTraversal(node){
  if(node === null){
    return
  }

  postOrderTraversal(node.left)
  postOrderTraversal(node.right)
  console.log(node.data)
}

postOrderTraversal(treeNode)

// 9 10 2 1 8 3

栈的思路

前序遍历

function preOrderTraversalWithStack(root){
  var stack = []
  var treeNode = root

  while(treeNode !== null || stack.length !== 0){
    while(treeNode !== null){
      console.log(treeNode.data)
      stack.push(treeNode)
      treeNode = treeNode.left
    }

    if(stack.length !== 0){
      treeNode = stack.pop()
      treeNode = treeNode.right
    }
  }
}

preOrderTraversalWithStack(treeNode)

// 3 2 9 10 8 1

中序遍历

function inOrderTraversalWithStack(root){
  var stack = []
  var treeNode = root

  while(treeNode !== null || stack.length !== 0){
    while(treeNode !== null){
      stack.push(treeNode)
      treeNode = treeNode.left
    }

    if(stack.length !== 0){
      treeNode = stack.pop()
      console.log(treeNode.data)
      treeNode = treeNode.right
    }
  }
}

inOrderTraversalWithStack(treeNode)

// 9 2 10 3 8 1

后序遍历

function postOrderTraversalWithStack(root){
  var stack = []
  var treeNode = root
  var lastNode

  while(treeNode !== null || stack.length !== 0){
    while(treeNode !== null){
      stack.push(treeNode)
      treeNode = treeNode.left
    }

    if(stack.length !== 0){
      treeNode = stack[stack.length - 1]
      
      if(lastNode === treeNode.right || treeNode.right === null){
        treeNode = stack.pop()
        console.log(treeNode.data)
        lastNode = treeNode
        treeNode = null
      }else if(treeNode.right !== null){
        treeNode = treeNode.right
      }
    }
  }
}

postOrderTraversalWithStack(treeNode)

// 9 10 2 1 8 3

广度优先遍历（层序遍历）

队列的思路

function levelOrderTraversal(root){
  var queue = []
  queue.push(root)

  while(queue.length !== 0){
    var node = queue.shift()
    console.log(node.data)

    if(node.left !== null){
      queue.push(node.left)
    }

    if(node.right != null){
      queue.push(node.right)
    }
  }
}

levelOrderTraversal(treeNode)

// 3 2 8 9 10 1

递归的思路

function levelOrderTraversalWithRecursion(root, index, res){
  if(root.left){
    levelOrderTraversalWithRecursion(root.left, 2 * index + 1, res)
  }

  if(root.right){
    levelOrderTraversalWithRecursion(root.right, 2 * index + 2, res)
  }

  res[index] = root.data
}

const res = []
levelOrderTraversalWithRecursion(treeNode, 0, res)
console.log(res)

// [3, 2, 8, 9, 10, 1]