相关概念

度、边：就是节点的分支数，以组成该树中各节点中最大的度作为该树的度。
叶子节点：度为零的节点
深度：组成该树各节点的最大层次
层次：根节点为第一层，它的字节点为第二层，依次类推
高度：叶子节高度为1，依次往上类推，树中结点最大高度就是树的高度
二叉树

特点：

每个节点最大度为 2
即使树中某个结点只有一个颗树，也要区分左子树和右子树

性质：

在二叉树的第 i 层最多有 2^(i-1) 个节点
二叉树中如果深度为 k ，那么最多有 2^k - 1 个节点（k>=1）
度为 0 的节点比度为 2 的节点多 1 个
节点数 = 边数 + 1
二叉树的遍历
一颗二叉树是由三部分组成的，分别是：根节点、左子树、右子树

注意，二叉树的左子树和右子树是必然存在的，不要看下面这张图只有一个节点就说它不是二叉树，它只不过是左、右子树都为空的二叉树而已。

在 JS 中我们可以使用下面的代码来创建一个二叉树 ```javascript function TreeNode(val) { this.val = val; this.left = null; this.right = null; }

const tree = new TreeNode(1) tree.left = new TreeNode(2); tree.right = new TreeNode(3);

二叉树的遍历分为：
- 先序遍历
- 中序遍历
- 后序遍历
- 层次遍历
按实现方式可以分为：
- 递归遍历（先序遍历、中序遍历、后序遍历）
- 迭代遍历（层次遍历）
先、中、后序遍历指的是根节点的遍历时机。
请写出下面的二叉树按照先、中、后序遍历的输出结果：<br />![Snip20211223_21.png](https://cdn.nlark.com/yuque/0/2021/png/21397267/1640233891536-3dff1b27-5c64-49e6-8096-e062852bcb3f.png#clientId=uad154bd6-bb2a-4&from=ui&id=u6b06956c&margin=%5Bobject%20Object%5D&name=Snip20211223_21.png&originHeight=352&originWidth=504&originalType=binary&ratio=1&size=104609&status=done&style=none&taskId=u3461ab01-d609-40b8-a11a-608cc82a28b)<br />上面这个二叉树的先序遍历、中序遍历、后续遍历的结果是什么呢？<br />先序遍历的结果：A、B、D、H、I、E、J、C、F、G<br />中序遍历的结果：H、D、I、B、J、E、A、F、C、G<br />后序遍历的结果：H、I、D、J、E、B、F、G、C、A
再来道练习题：<br />有颗二叉树，它的前序遍历结果是：1、2、4、9、5、6、10、3、7、8。它的中序遍历结果是：4、9、2、10、6、5、1、3、8、7。请画出这颗二叉树。
从前序遍历可以看到根节点是 1 ，从中序遍历可以得到 4、9、2、10、6、5 为左子树，3、8、7 为右子树。从先序遍历可以看到 2 为第二层的左变树的根，4、9为它左边的元素；3 为第二层右边树的根，3、8 为它右边的元素，依次类推得到下面的树：
```html
          1
      /      \
     2        3
  /     \      \
 4       5      7
  \     /        \
   9   6          8
      /
     10

从上面这个例子我们还可以得出中序遍历根的索引为 6，在先序遍历中索引 6，正好是二叉树左侧分支的所有元素，索引 6 往后的元素为二叉树右侧分支的元素。

二叉树的分类

根据不同的标准，二叉树可以分为完全二叉树、满二叉树。

满二叉树

如果叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。满二叉树每一层的叶子节点个数都是满的。

完全二叉树

叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

当根节点的编号从 1 开始，编号为 i 的子节点：左孩子标号为 2 i，右孩子编号为 2 i + 1。

我们可以用连续的空间存储。下面的二叉树用数组存储为：[A, B, C, D, E, F]

当根的编号从 0 开始，编号为 i 的子节点：左孩子标号为 2 i + 1，右孩子的编号为 2 i + 2。

有时也可以这样理解：节点指的是集合，边指的是关系。

二叉树的作用

二叉树分为左子树域和右子树域，即便最下面的叶子结点从图上看没有分叉，实际也是有左右子树的，只不过它们都为 null 或者 undefined。没有用到还要开辟空间，是浪费的。

假设有 k 叉树，n 个节点，浪费的指针：k n - (n - 1) = n (k - 1) + 1

以二叉树来说，根据上面的公式我们可以算出浪费的节点为：2 * n - (n - 1) = n + 1

我们可以使用左孩子右兄弟表示法，将多叉树转换成二叉树。自顶向下、自左向右，每一层按照孩子挂在它的左边，兄弟挂在孩子的右边的方法进行转换。

下面这个树转化成二叉树是什么样的呢？

通过左孩子右兄弟可以得出下面的转换结果：

练习递归

赋予一个函数明确含义，思考终止条件。

递归

前（先）序遍历

function preorder(root) {
    if (!root) return null;
  console.log(root.val);
  preorder(root.left);
  preorder(root.right);
}

中序遍历

function inorder(root) {
    if (!root) return null;
  preorder(root.left);
  console.log(root.val);
  preorder(root.right);
}

后序遍历

function postorder(root) {
    if (!root) return null;
  postorder(root.left);
  postorder(root.right);
    console.log(root.val);
}

迭代

前（先）序遍历

中序遍历

后序遍历

分享练习

589.N叉树的前序遍历

给定一个 N 叉树，返回其节点值的 前序遍历 。

N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。



进阶：

递归法很简单，你可以使用迭代法完成此题吗?



示例 1：



输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]
示例 2：


输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]


提示：

N 叉树的高度小于或等于 1000
节点总数在范围 [0, 10^4] 内


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var preorder = function (root) {
    if (!root) return [];
    let arr = [];
    let stack = [root];
    while (stack.length > 0) {
        let node = stack.pop();
        arr.push(node.val)
        for (let i = node.children.length - 1; i > -1; i--) {
            stack.push(node.children[i])
        }
    }
    return arr;
};

226.反转二叉树

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var invertTree = function (root) {
  if (!root) return root;
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
};

3.剑指offer32 从上到下打印二叉树II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。



例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]


提示：

节点总数 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var reverse = function(arr){
  let pre = 0;
  let tail = arr.length-1;
  while(pre < tail) {
    [arr[pre], arr[tail]] = [arr[tail], arr[pre]];
    pre++;
    tail--;
  }
  return arr;
}

var getNode = function(root, arr, k){
  if(!root) return null;
  arr[k] = arr[k] || [];
  arr[k].push(root.val);
  getNode(root.left, arr, k+1);
  getNode(root.right, arr, k+1);
}

var levelOrder = function(root) {
  let arr = [];

  getNode(root, arr, 0);
  return arr;
};

107.二叉树的层序遍历II

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其自底向上的层序遍历为：

[
  [15,7],
  [9,20],
  [3]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var reverse = function(arr){
  let pre = 0;
  let tail = arr.length-1;
  while(pre < tail) {
    [arr[pre], arr[tail]] = [arr[tail], arr[pre]];
    pre++;
    tail--;
  }
  return arr;
}

var getNode = function(root, arr, k){
  if(!root) return null;
  arr[k] = arr[k] || [];
  arr[k].push(root.val);
  getNode(root.left, arr, k+1);
  getNode(root.right, arr, k+1);
}

var levelOrderBottom = function(root) {
  let arr = [];

  getNode(root, arr, 0);
  return reverse(arr);
};

103.二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层序遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var getNode = function(root, arr, k){
  if(!root) return null;
  if(arr.length === k) arr.push([]);
  arr[k].push(root.val);
  getNode(root.left, arr, k+1);
  getNode(root.right, arr, k+1);
}
var reserve = function(arr){
  let pre = 0;
  let tail = arr.length-1;
  while(pre < tail){
    [arr[pre], arr[tail]] = [arr[tail], arr[pre]];
    pre++;
    tail--;
  }
}
var zigzagLevelOrder = function(root) {
  let arr = [];
  getNode(root, arr, 0);
  for (let i = 1; i < arr.length; i += 2) {
    reserve(arr[i]);
  }
  return arr;
};

105.从前序与中序遍历序列构造二叉树

给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。



示例 1:


Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]


提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

const buildNode = function (preorder, inorder) {
    if (!preorder.length) return null;

    const rootVal = preorder[0];
    const root = new TreeNode(rootVal);
    const index = inorder.indexOf(rootVal);
    const leftIn = inorder.slice(0, index);
    const rightIn = inorder.slice(index + 1);
    const leftPre = preorder.slice(1, index + 1);
    const rightPre = preorder.slice(index + 1);

    root.left = buildNode(leftPre, leftIn);
    root.right = buildNode(rightPre, rightIn);

    return root;
};

var buildTree = function (preorder, inorder) {
    return buildNode(preorder, inorder);
};

106.从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

const buildNode = function (inorder, postorder) {
    const len = postorder.length;
    if (!len) return null;
    const rootVal = postorder[len-1];
    const root = new ListNode(rootVal);
    const index = inorder.indexOf(rootVal);
    const leftIn = inorder.slice(0, index);
    const rightIn = inorder.slice(index + 1);
    const leftPost = postorder.slice(0, index);
    const rightPost = postorder.slice(index, len - 1);

    root.left = buildNode(leftIn, leftPost);
    root.right = buildNode(rightIn, rightPost);
    return root;
};
var buildTree = function (inorder, postorder) {
    return buildNode(inorder, postorder);
};

小册练习

144.二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。



示例 1：


输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：


输入：root = [1,2]
输出：[1,2]
示例 5：


输入：root = [1,null,2]
输出：[1,2]


提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归写法：

var preorderTraversal = function(root) {
    if (!root) return []
    const res = []
    preorder(root, res)
    return res
}

var preorder = function(node, res) {
    if (!node) return
    res.push(node.val)
    preorder(node.left, res)
    preorder(node.right, res)
}

迭代写法

102.二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。



示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var levelOrder = function(root) {
    const res = [];
    if (!root) return [];
    const queue = [];
    queue.push(root);

    while (queue.length) {
        const level = [];
        const len = queue.length;

        for (let i = 0; i < len; i++) {
            const top = queue.shift();
            level.push(top.val)
            if (top.left) {
                queue.push(top.left)
            }
            if (top.right) {
                queue.push(top.right);
            }
        }
        res.push(level);
    }
    return res;
};

参考

多叉树（森林）转二叉树

算法

4.树

相关概念

二叉树

二叉树的遍历

二叉树的分类

满二叉树

完全二叉树

二叉树的作用

练习递归

递归

前（先）序遍历

中序遍历

后序遍历

迭代

前（先）序遍历

中序遍历

后序遍历

分享练习

589.N叉树的前序遍历

226.反转二叉树

3.剑指offer32 从上到下打印二叉树II

107.二叉树的层序遍历II

103.二叉树的锯齿形层序遍历

105.从前序与中序遍历序列构造二叉树

106.从中序与后序遍历序列构造二叉树

小册练习

144.二叉树的前序遍历

102.二叉树的层序遍历

参考