二叉树的遍历

前序遍历

递归：

  1. function preorderTraversal(root) {
  2.   if (root === null) {
  3.     return
  4.   }
  6.   console.log(root.val)
  7.   inorderTraversal(root.left)
  8.   inorderTraversal(root.right)
  9. }

迭代：

  1. function preorderTraversal(root) {
  2.   const stack = [root]
  4.   while (stack.length > 0) {
  5.     const node = stack.pop()
  7.     if (node === null) {
  8.       continue
  9.     }
  11.     console.log(node.val)
  12.     stack.push(node.right)
  13.     stack.push(node.left)
  14.   }
  15. }

中序遍历：

递归：

  1. function inorderTraversal(root) {
  2.   if (root === null) {
  3.     return
  4.   }
  6.   inorderTraversal(root.left)
  7.   console.log(root.val)
  8.   inorderTraversal(root.right)
  9. }

迭代：

  1. function inorderTraversal(root) {
  2.   const stack = []
  4.   while (root || stack.length > 0) {
  5.     if (root) {
  6.       stack.push(root)
  7.       root = root.left
  8.     } else {
  9.         root = stack.pop()
  10.         console.log(root.val)
  11.         root = root.right
  12.     }
  13.   }
  14. }

后序遍历：

递归：

  1. function postorderTraversal(root) {
  2.   if (root === null) {
  3.     return
  4.   }
  6.   inorderTraversal(root.left)
  7.   inorderTraversal(root.right)
  8.   console.log(root.val)
  9. }

迭代：

  1. function postorderTraversal(root) {
  2.   const stack = []
  3.   let prev = null
  5.   while (root || stack.length > 0) {
  6.     if (root) {
  7.       stack.push(root)
  8.       root = root.left
  9.     } else {
  10.       root = stack.pop()
  11.       if (!root.right || root.right === prev) {
  12.         console.log(root.val)
  13.         prev = root
  14.         root = null
  15.       } else {
  16.         stack.push(root)
  17.         root = root.right
  18.       }
  19.     }
  20.   }
  21. }

层序遍历：

  1. function levelOrder(root) {
  2.   if (root === null) {
  3.     return
  4.   }
  6.   const queue = [root]
  7.   while (queue.length > 0) {
  8.     const node = queue.shift()
  9.     console.log(node.val)
  10.     if (node.left) {
  11.       queue.push(node.left)
  12.     }
  13.     if (node.right) {
  14.       queue.push(node.right)
  15.     }
  16.   }
  17. }

二叉搜索树
完美二叉树
满二叉树
线索二叉树