树和图最大的差别就是看有没有环。

    Linked List 是特殊化的 Tree，Tree 是特殊化的 Graph。

    二叉树遍历 Pre-order/In-order/Post-order。

    • 前序（Pre-order）：根-左-右
    • 中序（In-order）：左-根-右
    • 后序（Post-order）：左-右-根

    二叉树遍历可以使用递归或者栈的方式解决。

    1. // 前序遍历
    3. const preorder = (root) => {
    4.   if (!root) return;
    6.   console.log(root.val);
    8.   preorder(root.left);
    9.   preorder(root.right);
    10. }
    12. const preorder = (root) => {
    13.   if (!root) return;
    15.   const stack = [root];
    17.   while (stack.length) {
    18.     const n = stack.pop();
    20.     console.log(n.val);
    22.     if (n.right) stack.push(n.right);
    23.     if (n.left) stack.push(n.left);
    24.   }
    25. }
    1. // 中序遍历
    3. const inorder = (root) => {
    4.   if (!root) return;
    6.   inorder(root.left);
    7.   console.log(root.val);
    8.   inorder(root.right);
    9. }
    11. const inorder = (root) => {
    12.   if (!root) return;
    14.   const stack = [];
    16.   let p = root;
    18.   while (stack.length || p) {
    19.     while (p) {
    20.       stack.push(p);
    21.       p = p.left;
    22.     }
    24.     const n = stack.pop();
    25.     console.log(n.val);
    27.     p = n.right;
    28.   }
    29. }
    1. // 后序遍历
    3. const postorder = (root) => {
    4.   if (!root) return;
    6.   postorder(root.left);
    7.   postorder(root.right);
    8.   console.log(root.val);
    9. }
    11. const postorder = (root) => {
    12.   if (!root) return;
    14.   const outputStack = [];
    15.   const stack = [root];
    17.   while (stack.length) {
    18.     const n = stack.pop();
    20.     outputStack.push(n);
    22.     if (n.left) stack.push(n.left);
    23.     if (n.right) stack.push(n.right);
    24.   }
    26.   while (outputStack.length) {
    27.     const n = outputStack.pop();
    28.     console.log(n.val);
    29.   }
    30. }

    普通的树遍历的话都是 O(n) 的时间复杂度，和链表没有太大区别。

    二叉搜索树（Binary Search Tree），也称二叉排序树、有序二叉树（Ordered Binary Tree）、排序二叉树（Sorted Binary Tree），是指一棵空树或者具有下列性质的二叉树。

    • 左子树上所有结点的值均小于它的根结点的值
    • 右子树上所有结点的值均大于它的根结点的值
    • 以此类推：左、右子树也分别为二叉查找树

    中序遍历：升序排列

    二叉搜索树的时间复杂度是 O(log n)，极端情况下会退化到 O(n)。

    二叉搜索树查询、插入、删除 Demo 演示： https://visualgo.net/zh/bst

    二叉树的中序遍历（亚马逊、微软、字节跳动在半年内面试中考过）

    二叉树的前序遍历（谷歌、微软、字节跳动在半年内面试中考过）

    N 叉树的后序遍历（亚马逊在半年内面试中考过）

    N 叉树的前序遍历（亚马逊在半年内面试中考过）

    N 叉树的层序遍历

    1. // 二叉树的中序遍历
    3. // 思路1：递归解法，复杂度 O(n)
    4. // 思路2：迭代解法，维护一个栈，复杂度 O(n)
    6. /**
    7.  * @param {TreeNode} root
    8.  * @return {number[]}
    9.  */
    10. var inorderTraversal = function(root) {
    11.   if (!root) return [];
    13.   const res = [];
    15.   const inorder = (root) => {
    16.     root.left && inorder(root.left); 
    17.     res.push(root.val);
    18.     root.right && inorder(root.right); 
    19.   }
    21.   inorder(root);
    23.   return res;
    24. };
    26. /**
    27.  * @param {TreeNode} root
    28.  * @return {number[]}
    29.  */
    30. var inorderTraversal = function(root) {
    31.   const res = [];
    32.   const stack = [];
    34.   while (root || stack.length) {
    35.     while (root) {
    36.       stack.push(root);
    37.       root = root.left;
    38.     }
    40.     root = stack.pop();
    41.     res.push(root.val);
    42.     root = root.right;
    43.   }
    45.   return res;
    46. };
    1. // 二叉树的前序遍历
    3. /**
    4.  * @param {TreeNode} root
    5.  * @return {number[]}
    6.  */
    7. var preorderTraversal = function(root) {
    8.   if (!root) return [];
    10.   const res = [];
    12.   const preorder = (root) => {
    13.     res.push(root.val);
    14.     root.left && preorder(root.left);
    15.     root.right && preorder(root.right);
    16.   }
    18.   preorder(root);
    20.   return res;
    21. };
    23. /**
    24.  * @param {TreeNode} root
    25.  * @return {number[]}
    26.  */
    27. var preorderTraversal = function(root) {
    28.   if (!root) return [];
    30.   const stack = [root];
    31.   const res = [];
    33.   while (stack.length) {
    34.     const curr = stack.pop();
    36.     res.push(curr.val);
    38.     curr.right && stack.push(curr.right);
    39.     curr.left && stack.push(curr.left);
    40.   }
    42.   return res;
    43. };
    1. // N 叉树的后序遍历
    3. /**
    4.  * @param {Node|null} root
    5.  * @return {number[]}
    6.  */
    7. var postorder = function(root) {
    8.   if (!root) return [];
    10.   const res = [];
    12.   const _postorder = (root) => {
    13.     root.children && root.children.forEach(_postorder);
    14.     res.push(root.val);
    15.   }
    17.   _postorder(root);
    19.   return res;
    20. };
    22. /**
    23.  * @param {Node|null} root
    24.  * @return {number[]}
    25.  */
    26. var postorder = function(root) {
    27.   if (!root) return [];
    29.   const res = [];
    30.   const stack = [root];
    32.   while (stack.length) {
    33.     const curr = stack.pop();
    35.     res.push(curr.val);
    37.     curr.children && stack.push(...curr.children);
    38.   }
    40.   return res.reverse();
    41. };
    1. // N 叉树的前序遍历
    3. /**
    4.  * @param {Node|null} root
    5.  * @return {number[]}
    6.  */
    7. var preorder = function(root) {
    8.   if (!root) return [];
    10.   const res = [];
    12.   const _preorder = (root) => {
    13.     res.push(root.val);
    14.     root.children && root.children.forEach(_preorder);
    15.   }
    17.   _preorder(root);
    19.   return res;
    20. };
    22. /**
    23.  * @param {Node|null} root
    24.  * @return {number[]}
    25.  */
    26. var preorder = function(root) {
    27.   if (!root) return [];
    29.   const res = [];
    30.   const stack = [root];
    32.   while (stack.length) {
    33.     const curr = stack.pop();
    35.     res.push(curr.val);
    36.     curr.children && stack.push(...curr.children.reverse());    
    37.   }
    39.   return res;
    40. };
    1. // N 叉树的层序遍历
    3. /**
    4.  * @param {Node|null} root
    5.  * @return {number[][]}
    6.  */
    7. var levelOrder = function(root) {
    8.   if (!root) return [];
    10.   const res = [];
    12.   const _levelorder = (root, level) => {
    13.     res[level] ? res[level].push(root.val) : res[level] = [root.val];
    14.     root.children && root.children.forEach(curr => _levelorder(curr, level + 1));
    15.   }
    17.   _levelorder(root, 0);
    19.   return res;
    20. };
    22. /**
    23.  * @param {Node|null} root
    24.  * @return {number[][]}
    25.  */
    26. var levelOrder = function(root) {
    27.   if (!root) return [];
    29.   const res = [];
    30.   const queue = [root];
    32.   while (queue.length) {
    33.     const len = queue.length;
    34.     const level = [];
    36.     for (let i = 0; i < len; i++) {
    37.       const curr = queue.shift();
    39.       level.push(curr.val);
    41.       queue.push(...curr.children);
    42.     }
    44.     res.push(level);
    45.   }
    47.   return res;
    48. };