数据结构与算法之二叉树篇

对于树这个结构，最常见的就是二叉树。我们除了需要了解二叉树的基本操作之外，还需要了解一些特殊的二叉树，比如二叉搜索树、平衡二叉树等，另外还要熟悉二叉树的遍历方式，比如前序遍历、中序遍历、后序遍历、层序遍历。另外还要知道二叉树的常用遍历的方式：深度优先遍历和广度优先遍历。

1. 二叉树的概念

关于“树”，有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。它们的定义是这样的：

• 节点的高度：节点到叶子节点的最长路径（边数）
• 节点的深度：根节点到这个节点所经历的边的个数
• 节点的层数：节点的深度 +1
• 树的高度：根节点的高度

（1）二叉树

二叉树（binary tree）是一种特殊的树，它是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

二叉树具有以下特点：

• 每个结点最多有两颗子树，结点的度最大为2（一个节点含有的子树的个数称为该节点的度）。
• 左子树和右子树是有顺序的，顺序不能颠倒。
• 即使某结点只有一个子树，也要区分左右子树。

存储二叉树有两种方法，

• 基于指针或者引用的二叉链式存储法，
• 基于数组的顺序存储法。

1）链式存储法。
从下图可以看到，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式比较常用。大部分二叉树代码都是通过这种结构来实现的。

2）顺序存储法。
把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 i = 2 的位置，右子节点存储在 2 i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 i = 2 2 = 4 的位置，右子节点存储在 2 i + 1 = 2 2 + 1 = 5 的位置。

如果节点 X 存储在数组中下标为 i 的位置，下标为 2 i 的位置存储的就是左子节点，下标为 2 i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。

不过，上面是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。看下面这个例子：

所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

（2）满二叉树

所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树。就是完美圆满的意思，关键在于树的平衡。

根据满二叉树的定义，得到其特点为：

1. 叶子只能出现在最下一层。
2. 非叶子结点度一定是2。

3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

   （3）完全二叉树

   对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。满二叉树必须是完全二叉树，反过来不一定成立。其中关键点是按层序编号，然后对应查找。下图就是一个完全二叉树：
   
   结合完全二叉树定义得到其特点：

4. 叶子结点只能出现在最下一层（满二叉树继承而来）

5. 最下层叶子结点一定集中在左 部连续位置。
6. 倒数第二层，如有叶子节点，一定出现在右部连续位置。
7. 同样结点树的二叉树，完全二叉树的深度最小（满二叉树也是对的）。

完全二叉树的性质：

1. 具有 n 个结点的完全二叉树的深度为 K =「log2n」+1(取下整数)
2. 有 n 个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系： 若 i 为结点编号（从1开始编号）则 如果 i>1，则其父结点的编号为 i/2；
3. 完全二叉树，如果 2 i <= n，则其左儿子（即左子树的根结点）的编号为2 i；若2 i > n，则无左儿子；如果 2 i + 1 <= n，则其右儿子的结点编号为 2 i + 1；若 2 i + 1 > n，则无右儿子。

   （4）二叉查找树

   二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。

二叉查找树的根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，这一规则适用于二叉查找树中的每一个节点。下图就是二叉查找树：

二叉排序树要么是空二叉树，要么具有如下特点：

• 如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
• 如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
• 左右子树也要求都是二叉排序树；
• 在二叉查找树中，会尽可能规避两个结点数值相等的情况；
• 对二叉查找树进行中序遍历，就可以输出一个从小到大的有序数据队列。

在利用二叉查找树执行查找操作时，可以进行以下判断：

• 首先判断根结点是否等于要查找的数据，如果是就返回。
• 如果根结点大于要查找的数据，就在左子树中递归执行查找动作，直到叶子结点。
• 如果根结点小于要查找的数据，就在右子树中递归执行查找动作，直到叶子结点。
• 这样的“二分查找”所消耗的时间复杂度就可以降低为 O(logn)。

  （5）平衡二叉查找树（AVL）

  平衡二叉查找树具有如下几个性质：

1. 可以是空树。
2. 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1。

上图就是一棵平衡二叉树。

平衡二叉树是为了解决二叉查找树中出现链式结构（只有左子树或只有右子树）的情况，这样的情况出现后对我们的查找没有一点帮助，反而增加了维护的成本。

平衡因子使用两个字母来表示。第一个字母表示最小不平衡子树根结点的平衡因子，第二个字母表示最小不平衡子树较高子树的根结点的平衡因子。根据不同的情况使用不同的方法来调整失衡的子树。

2. 二叉树的操作

对于二叉树这个数据结构，只有解决了遍历问题，才能通过树来进行数据的增删查操作。所谓的二叉树遍历指的是：从树的根节点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问仅且一次。

常见的二叉树遍历方式有前序遍历、中序遍历、后序遍历和层序遍历，每种遍历方法都可以用递归和迭代的方式来实现，这里的序指的是父结点的遍历顺序，前序就是先遍历父结点，中序就是中间遍历父结点，后序就是最后遍历父结点。其中前序遍历、中序遍历、后序遍历是基于深度优先遍历的，层序遍历是基于广度优先遍历的。

上图中二叉树的结构及其编码：

const root = {
  val: "A",
  left: {
    val: "B",
    left: {
      val: "D"
    },
    right: {
      val: "E"
    }
  },
  right: {
    val: "C",
    left: {
      val: "F"
    },
    right: {
      val: "G"
    }
  }
};

（1）前序遍历

基本思想：先访问根结点，再先序遍历左子树，最后再先序遍历右子树，即根—左—右。
遍历结果：A -> B -> D -> E -> C -> F

1）递归实现：

function preorder(root){
  if(!root){
     return
  }
  console.log(root.val)  // 打印当前遍历的节点
  preorder(root.left)    // 递归遍历左子树
  preorder(root.right)   // 递归遍历右子树
}

2）非递归实现：
初始化一个栈和结果数组，将根节点放入栈中，当栈不为空时，重复下面的步骤：
（1）取出栈顶元素top，访问top
（2）若top的右子节点不为空，将top的右子节点放入栈中
（3）若top的左子节点不为空，将top的左子节点放入栈中
（4）将取出的栈顶元素top放入结果数组

function preorder(root){
    if(!root){
       return [];
    }
    var result = []
    var stack = [root]
    while(stack.length){
       var top = stack.pop();
       if(top.right){
          stack.push(top.right);
       }
       if(top.left){
          stack.push(top.left);
       }
       result.push(top.val);
    }
    return result;
}

（2）中序遍历

基本思想：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树，即左—根—右。
遍历结果：D -> B -> E -> A -> C -> F

1）递归实现：

function inorder(root) {
    if(!root) {
        return 
    }
    inorder(root.left)       // 递归遍历左子树 
    console.log(root.val)    // 打印当前遍历的结点
    inorder(root.right)      // 递归遍历右子树  
}

2）非递归实现：
初始化一个栈和结果数组，当栈不为空时，重复下面的步骤：
（1）将根节点和所有的左子节点放入栈中，直到没有左子节点
（2）栈顶元素出栈，存入结果数组，将出栈的元素作为根节点
（3）查看该根节点右子节点是否有左子节点，若有就入栈，否则继续出栈

function inorder(root) {
   if(!root){
       return [];
    }
    var result = []
    var stack = []
    while(stack.length || root){
        while(root){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        result.push(root.val)
        root = root.right;
      }
      return result;
}

（3）后序遍历

基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点，即左—右—根。
遍历结果：D -> E -> B -> F -> C -> A

1）递归实现：

function postorder(root) {
    if(!root) {
        return 
    }
    inorder(root.left)       // 递归遍历左子树 
    inorder(root.right)      // 递归遍历右子树 
    console.log(root.val)    // 打印当前遍历的结点 
}

2）非递归实现：
初始化一个栈和结果数组，将根节点放入栈中，当栈不为空时，重复下面的步骤：
（1）取出栈顶元素top，访问top
（2）将取出的栈顶元素top放入结果数组的最开始
（3）若top的左子节点不为空，将top的左子节点放入栈中
（4）若top的右子节点不为空，将top的右子节点放入栈中

function postorder(root) {
    if(!root){
       return [];
    }
    var result = []
    var stack = [root]
    while(stack.length){
       var top = stack.pop();
       result.unshift(top.val);
       if(top.left){
          stack.push(top.left);
       }
       if(top.right){
          stack.push(top.right);
       } 
    }
    return result;
}

（4）层序遍历

基本思想：层序遍历就是从上到下，从左到右打印二叉树的节点。
遍历结果：A -> B -> C -> D -> E -> F

创建一个数组存放结果，一个队列存放二叉树的节点，如果存放二叉树的队列不为空，就重复下面的步骤：
（1）将队列的第一个节点作为根节点，并放入结果数组中
（2）如果该根节点的左子树不为空，就将其放入队列中
（3）如果该根节点的右子树不为空，就将其放入队列中

基本实现：

function levelTraversal(root){
   if(!root){
       return [];
    }
   var queue = [root];
   var result = [];
   while (queue.length){
      var node = queue.shift();
      result.push(node.val);
      if(node.left){
          queue.push(node.left);
      }
      if(node.right){
          queue.push(node.right);
      }
   }
   return result; 
}

（5）总结

可以看到，二叉树遍历过程中，每个结点都被访问了一次，其时间复杂度是 O(n)。接着，在找到位置后，执行增加和删除数据的操作时，只需要通过指针建立连接关系就可以了。对于没有任何特殊性质的二叉树而言，抛开遍历的时间复杂度以外，真正执行增加和删除操作的时间复杂度是 O(1)。树数据的查找操作和链表一样，都需要遍历每一个数据去判断，所以时间复杂度是 O(n)。

3. 经典题目：二叉树的遍历

（1）二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 
输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

迭代实现：初始化一个栈和结果数组，将根节点放入栈中，当栈不为空时，重复下面的步骤：
（1）取出栈顶元素top，访问top
（2）若top的右子节点不为空，将top的右子节点放入栈中
（3）若top的左子节点不为空，将top的左子节点放入栈中
（4）将取出的栈顶元素top放入结果数组

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 迭代的写法：
var preorderTraversal = function(root) {
  if(!root){
       return [];
    }
    var result = []
    var stack = [root]
    while(stack.length!==0){
       var top = stack.pop();
       if(top.right){
          stack.push(top.right);
       }
       if(top.left){
          stack.push(top.left);
       }
       result.push(top.val);
    }
    return result;
};
// 递归的写法：
var preorderTraversal = function(root) {
  if(!root){
    return [];
  }
  var result = []
  var preorderTraversalNode = (node) => {
      if(node) {
          result.push(node.val)
          preorderTraversalNode(node.left)
          preorderTraversalNode(node.right)
       }
   }
  preorderTraversalNode(root)
  return result
};

迭代的复杂度：

• 时间复杂度，每个结点都入栈出栈一次，遍历整棵树的时间复杂度为 O(N)，N表示二叉树的节点数。
• 空间复杂度就是栈的最大使用空间，而这个空间是由树的高度决定的，所以空间复杂度就是 O(H)，H 表示二叉树的高度。

递归的复杂度：

• 时间复杂度，树上的每个结点都只访问一次，并且每次访问都只有一次压栈弹栈操作，所以复杂度为 O(N)，N表示二叉树的节点数。
• 空间复杂度，由于函数调用栈的深度与树的高度有关系，所以使用的空间为 O(H)。H 表示二叉树的高度。

  （2）二叉树的中序遍历

  给定一个二叉树，返回它的 中序 遍历。示例:

  输入: [1,null,2,3]
   1
    \
     2
    /
   3
  输出: [1,3,2]

  进阶: 递归算法很简单，你可以通过迭代算法完成吗？

迭代实现：初始化一个栈和结果数组，当栈不为空时，重复下面的步骤：
（1）将根节点和所有的左子节点放入栈中，直到没有左子节点
（2）栈顶元素出栈，存入结果数组，将出栈的元素作为根节点
（3）查看该根节点右子节点是否有左子节点，若有就入栈，否则继续出栈

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 迭代的实现：
var inorderTraversal = function(root) {
    if(!root){
       return [];
    }
    var result = []
    var stack = []
    while(stack.length!==0||root){
        while(root){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        result.push(root.val)
        root = root.right;
      }
      return result;
};
// 递归的实现
var inorderTraversal = function(root) {
    if(!root){
       return [];
    }
    var result = []
    var inorderTraversalNode = (node) => {
        if(node) {  
            inorderTraversalNode(node.left)
            result.push(node.val)
            inorderTraversalNode(node.right)
         }
     }
    inorderTraversalNode(root)
    return result
};

迭代的复杂度：

• 时间复杂度，每个结点都入栈出栈一次，遍历整棵树的时间复杂度为 O(N)，N表示二叉树的节点数。
• 空间复杂度就是栈的最大使用空间，而这个空间是由树的高度决定的，所以空间复杂度就是 O(H)，H 表示二叉树的高度。

递归的复杂度：

• 时间复杂度，树上的每个结点都只访问一次，并且每次访问都只有一次压栈弹栈操作，所以复杂度为 O(N)，N表示二叉树的节点数。
• 空间复杂度，由于函数调用栈的深度与树的高度有关系，所以使用的空间为 O(H)。H 表示二叉树的高度。

  （3）二叉树的后序遍历

  给定一个二叉树，返回它的后序遍历。示例:

  输入: [1,null,2,3]  
   1
    \
     2
    /
   3 
  输出: [3,2,1]

  进阶: 递归算法很简单，你可以通过迭代算法完成吗？

迭代实现：二叉树的后序遍历和前序遍历是一个相反的过程，所以基本思路和前序遍历类似。初始化一个栈和结果数组，将根节点放入栈中，当栈不为空时，重复下面的步骤：
（1）取出栈顶元素top，访问top
（2）将取出的栈顶元素top放入结果数组的最开始
（3）若top的左子节点不为空，将top的左子节点放入栈中
（4）若top的右子节点不为空，将top的右子节点放入栈中

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 迭代的实现：
var postorderTraversal = function(root) {
    if(!root){
       return [];
    }
    var result = []
    var stack = [root]
    while(stack.length!==0){
       var top = stack.pop();
       result.unshift(top.val);
       if(top.left){
          stack.push(top.left);
       }
       if(top.right){
          stack.push(top.right);
       }
    }
    return result;
};
// 递归的实现
var postorderTraversal = function(root) {
    if(!root){
       return [];
    }
    var result = []
    var postorderTraversalNode = (node) => {
        if(node) {  
            postorderTraversalNode(node.left)
            result.push(node.val)
            postorderTraversalNode(node.right)
         }
     }
    postorderTraversalNode(root)
    return result
};

迭代的复杂度：

• 时间复杂度，每个结点都入栈出栈一次，遍历整棵树的时间复杂度为 O(N)，N表示二叉树的节点数。
• 空间复杂度就是栈的最大使用空间，而这个空间是由树的高度决定的，所以空间复杂度就是 O(H)，H 表示二叉树的高度。

递归的复杂度：

• 时间复杂度，树上的每个结点都只访问一次，并且每次访问都只有一次压栈弹栈操作，所以复杂度为 O(N)，N表示二叉树的节点数。

• 空间复杂度，由于函数调用栈的深度与树的高度有关系，所以使用的空间为 O(H)。H 表示二叉树的高度。

  （4）二叉树的层序遍历

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

  二叉树：[3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

  返回其层次遍历结果：

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

  创建一个数组存放结果，一个队列存放二叉树的节点，根据输出的要求，设置一个level，储存当前层数，如果存放二叉树的队列不为空，就重复下面的步骤：
  （1）将队列的第一个节点作为根节点，并放入当前层的结果数组中
  （2）如果该根节点的左子树不为空，就将其放入队列中
  （3）如果该根节点的右子树不为空，就将其放入队列中
  （4）遍历完该层之后，就遍历下一层

  /**
  * Definition for a binary tree node.
  * function TreeNode(val) {
  *     this.val = val;
  *     this.left = this.right = null;
  * }
  */
  /**
  * @param {TreeNode} root
  * @return {number[][]}
  */
  var levelOrder = function(root) {
   if(!root){
       return [];
    }
   var queue = [root];
   var result = [];
   var level = 0;
   while (queue.length!==0){
       result[level]=[];
       var levelNum = queue.length;
       while(levelNum--){
            var node = queue.shift();
            result[level].push(node.val);
            if(node.left){
               queue.push(node.left);
             }
            if(node.right){
               queue.push(node.right);
            }
        } 
        level++;
    }
   return result; 
  };

  复杂度分析：

• 时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)，其中n是二叉树的节点数。

• 空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)，其中n是二叉树的节点数。

  （5）二叉树的层次遍历 II

  给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。例如：给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

  返回其自底向上的层次遍历为：

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

  对于这道题目，对二叉树进行层序遍历，最直接的方法就是使用BFS（广度优先遍历）。

首先创建一个队列，将当前节点放进去，队列中的节点始终是当前层的节点。按顺序出列，加入结果中，并将当前节点的子节点加入到队列中。重复上述步骤，直到队列为空，就遍历完了整个二叉树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    if(!root) {
        return []
    }
    const queue = []
    queue.push(root)
    const res = []  // 用来储存最后的结果
    while(queue.length){
        const subRes = []  // 用来储存每一层的节点值
        const levelSize = queue.length
        for(let i = 0; i < levelSize; i++){
            const cur = queue.shift()
            subRes.push(cur.val)
            if(cur.left){
                queue.push(cur.left)
            }
            if(cur.right){
                queue.push(cur.right)
            }
        }
        res.unshift(subRes)
    }
    return res
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是二叉树中的节点数。每个节点访问一次，结果列表使用链表的结构时，在结果列表头部添加一层节点值的列表的时间复杂度是 O(1)，因此总时间复杂度是 O(n)。
• 空间复杂度：O(n)，其中 n 是二叉树中的节点数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。

  （6）二叉树的锯齿形层序遍历

  给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。例如：给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

  返回锯齿形层次遍历如下：

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

  可以采用递归的方式来解答，每一层都创建一个数组，奇数层从左往右依次插入数组，偶数层从右往左依次插入数组。

思路不是很难，这里我们使用i & 1来判断层数的奇偶：

i & 1 == 1  // 奇数
i & 1 == 0  // 偶数

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    const res = []
    function dfs(i, current){
        if(!current) return 
        if(!Array.isArray(res[i])){
            res[i] = []
        }
        if(i & 1){
            res[i].unshift(current.val)
        }else{
            res[i].push(current.val)
        }
        dfs(i + 1, current.left)
        dfs(i + 1, current.right)
    }
    dfs(0, root)
    return res
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 为二叉树的节点数。每个节点会且仅会被遍历一次，时间复杂度为 O(n)。
• 空间复杂度：O(n)，其中 n 为二叉树的节点数。我们需要维护存储节点的队列和存储节点值的双端队列，空间复杂度为 O(n)。

  4. 经典题目：二叉树的属性

  （1）二叉树的完全性校验

  给定一个二叉树，确定它是否是一个完全二叉树。百度百科中对完全二叉树的定义如下：

  若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2 个节点。）

示例 1：

输入：[1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。

示例 2：

输入：[1,2,3,4,5,null,7]
输出：false
解释：值为 7 的结点没有尽可能靠向左侧。

提示：树中将会有 1 到 100 个结点。

对于这道题目，我们可以使用层序遍历来解决。在层序遍历的过程中，需要用一个index来维护节点的索引，如果一个节点的index，那它的左孩子的索引是index * 2，右孩子的索引是index * 2 + 1。

这里我们初始化一个队列，用来存储当前节点node和当前节点的索引值index。使用一个count来记录当前已经遍历到第几个节点。如果当前节点的索引值index和count + 1相等，那么说明当前节点的位置时正确的，就继续遍历，如果不相等，说明中间缺少了节点，直接返回false，结束遍历。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isCompleteTree = function(root) {
    if(!root){
        return true
    }
    let count = 0
    const queue = [{ node: root, index: 1 }]
    while(queue.length){
        const temp = queue.shift()
        const node = temp.node 
        const index = temp.index
        // 判断当前节点是否是正确的顺序值
        if(index !== ++count){
            return false
        }
        // 遍历当前节点的左右子树
        node.left && queue.push({node: node.left, index: index * 2})
        node.right && queue.push({node: node.right, index: index * 2 + 1})
    }
    return true
};

复杂度分析：

• 时间复杂度：O(n)，这里最坏的情况就是我们需要遍历整棵二叉树，所以时间复杂度为O(n)，其中n是二叉树的节点数；
• 空间复杂度：O(1)，我们需要初始化一个队列来保存当前遍历的节点，这个队列是一个常数空间，所以空间复杂度为O(1)。

  （2）二叉树中的最大路径和

  给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
  示例 1：

  输入：[1,2,3]
       1
      / \
     2   3
  输出：6

  示例 2：

  输入：[-10,9,20,null,null,15,7]
   -10
   / \
  9  20
    /  \
   15   7
  输出：42

  对于这道题目，我们可以使用递归遍历二叉树，我们需要的是最大的路径和，所以某个节点左右子树路径和和这个节点的值的和的最大值就是我们要求的解。

需要注意：

• 一条从父节点延伸下来的路径，只能进入左子树或者右子树，不能同时进入左右子树。

• 只有在最大贡献值大于 0 时，才会选取对应子节点。

  /**
  * Definition for a binary tree node.
  * function TreeNode(val) {
  *     this.val = val;
  *     this.left = this.right = null;
  * }
  */
  /**
  * @param {TreeNode} root
  * @return {number}
  */
  var maxPathSum = function(root) {
    let sum = Number.MIN_SAFE_INTEGER
    const dfs = (root) => {
        if(!root){
            return 0
        }
        // 计算左右子树的最大路径和
        const left = dfs(root.left)
        const right = dfs(root.right)
        // 计算总的最大路径和
        const maxSum = left + root.val + right
        sum = Math.max(sum, maxSum)
        // 返回当前计算出的最大路径
        const max = root.val + Math.max(left, right)
        return max < 0 ? 0 : max
    }
    dfs(root)
    return sum
  };

  复杂度分析：

• 时间复杂度：O(N)，其中 N 是二叉树中的节点个数。对每个节点访问不超过 2 次。

• 空间复杂度：O(N)，其中 N 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。

  （3）二叉树的直径

  给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。示例：给定二叉树

        1
       / \
      2   3
     / \     
    4   5

  返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

遇到二叉树的问题，我们在遍历时通常是采用深度优先遍历和广度优先遍历，这里需要求直径，我们就使用到了深度优先遍历。

从根节点进行遍历，在遍历到每个节点的时候，将其左右子树的最大深度加在一起，与结果res对比，并将最大的值赋值给热搜，这样使res一直保持是最大的值。最后返回res即可。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) { 
    let res = 0
    function depth(rootNode){
        if(!rootNode) return 0
        let l = depth(rootNode.left)  // l为左子树的深度
        let r = depth(rootNode.right) // r为右子树的深度
        res = Math.max(res, l + r)    // 计算最大直径l+r，更新res，能保持其一直是最大值
        return Math.max(l ,r) + 1     // 返回以该节点为根的子树的深度
    }
    depth(root)
    return res
};

复杂度分析：

• 时间复杂度：O(n)，其中n为二叉树的节点数，这里需要遍历整棵二叉树，所以时间复杂度为O(n)。

• 空间复杂度：O(h)，其中h是二叉树的最大深度，是一个常数变量。

  （4）二叉树的所有路径

  给定一个二叉树，返回所有从根节点到叶子节点的路径。说明: 叶子节点是指没有子节点的节点。示例: ```javascript 输入:

  1 / \ 2 3 \ 5

输出: [“1->2->5”, “1->3”]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

这个题目就是对二叉树数进行深度优先遍历，在遍历的过程中将当前节点的值存储在字符串中，直到没有子节点，就将这个遍历出的结果字符串存入结果数组中。
```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    if(!root) return []
    let res = []
    const buildPath = (root, resStr) => {
        if(!root.left && !root.right){
            resStr += root.val
            res.push(resStr)
            return 
        }
        resStr += root.val + '->'
        if(root.left){
            buildPath(root.left, resStr)
        }
        if(root.right){
            buildPath(root.right, resStr)
        }
    }
    buildPath(root, '')
    return res
};

复杂度分析

• 时间复杂度：O(N2)，其中 N 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(N)，故时间复杂度为 O(N2)；
• 空间复杂度：O(N2)，其中 N 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。在最坏情况下，当二叉树中每个节点只有一个孩子节点时，即整棵二叉树呈一个链状，此时递归的层数为 N，此时每一层的 path 变量的空间代价的总和的空间复杂度为 O(N2)，最好情况下，当二叉树为平衡二叉树时，它的高度为 logN，此时空间复杂度为O((logN)2)。

  （5）对称的二叉树

  给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
  / \ / \
  3  4 4  3

  但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:5r

    1
   / \
  2   2
   \   \
   3    3

  进阶：你可以运用递归和迭代两种方法解决这个问题吗？

递归的思路比较简单，具体实现思路如下：

• 首先判断当前树是否为空，空则直接返回true，否则就左子树的左子树和右子树的右子树是否相等
• 如果左节点或者右节点为空时，就比较对应的右节点或左节点是否为空，为空则返回true，否则就返回false
• 如果左右节点都不为空，就判断左节点的左节点和右节点的右节点是否相等
• 如果相等，就传入该节点的子节点进行递归，否则就返回false

迭代方法需要借助队列来实现，具体实现思路如下：通过「同步移动」两个指针的方法来遍历这棵树，l 指针和 r 指针一开始都指向这棵树的根，随后 l 右移时，r 左移，l 左移时，r 右移。每次检查当前 l 和 r 节点的值是否相等，如果相等再判断左右子树是否对称。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
// 迭代的实现
const isSymmetric = (root) => {
  if (!root) return true
  let queue = [root.left, root.right]
  while (queue.length > 0) {
    let node1 = queue.shift(), node2 = queue.shift()
    if (node1 === null && node2 === null) continue
    if (node1 === null || node2 === null || node1.val !== node2.val) return false
    queue.push(node1.left, node2.right, node1.right, node2.left)
  }
  return true
}
// 递归的实现
var isSymmetric = function(root) {
    if(!root){
        return true
    }
    return isSameTree(root.left, root.right)
};
const isSameTree = (l, r) => {
    if(!l) return r === null
    if(!r) return l === null
    if(l.val !== r.val) return false
    return isSameTree(l.left, r.right,) && isSameTree(l.right, r.left)
}

递归实现的复杂度分析：

• 时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)，其中n是这棵树的节点数。
• 空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。

迭代实现的复杂度分析：

• 时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)，其中n是这棵树的节点数。
• 空间复杂度：这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。

  （6）二叉树的层平均值

  给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。示例 1：

  输入：
    3
   / \
  9  20
    /  \
   15   7
  输出：[3, 14.5, 11]
  解释：
  第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

  提示：节点值的范围在32位有符号整数范围内。

这是一道比较简单的题目，就是二叉树的层序遍历。这里使用BFS（广度优先遍历），在遍历的过程中，将每层的节点值保存在队列中，然后将所有值出栈并相加。除以当前层的队列的长度就是这一层的平均值。将其放入结果中。重复上述步骤，直到遍历完整棵二叉树，返回最后的结果。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var averageOfLevels = function(root) {
    if(!root){
        return []
    }
    const res = []
    const queue = []
    queue.push(root)
    while(queue.length){
        const len = queue.length
        let sum = 0
        for(let i = 0; i < len; i++){
            const cur = queue.shift()
            sum += cur.val
            if(cur.left){
                queue.push(cur.left)
            }
            if(cur.right){
                queue.push(cur.right)
            }
        }
        res.push(sum / len)
    }
    return res
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是二叉树中的节点个数。广度优先搜索需要对每个节点访问一次，时间复杂度是 O(n)。需要对二叉树的每一层计算平均值，时间复杂度是 O(h)，其中 h 是二叉树的高度，任何情况下都满足h≤n。因此总时间复杂度是 O(n)。

• 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。

  （7）二叉树的右视图

  给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。示例:

  输入: [1,2,3,null,5,null,4]
  输出: [1, 3, 4]
  解释:
   1            <---
  /   \
  2     3         <---
  \     \
  5     4       <---

  对于二叉树的题目，最常用的方法就是深度优先遍历（DFS）和广度优先遍历（BFS）。下面就来用这两种方法来解决这个问题。

DFS：

• 设置一个level，来保存当前遍历的二叉树的层级，初始值为0
• 由于我们需要返回的是右视图的节点值，所以先遍历右节点的值，将右节点保存在结果数组中
• 然后遍历左节点
• 当结果数组的长度和二叉树当前的层级相同时，就将当前的节点值保存
• 重复上述步骤，直至遍历完二叉树的所有节点

BFS：
使用广度优先遍历来遍历二叉树，这就相当于二叉树的层序遍历，对于每一层的遍历结果，取最后一个即可，这里我们使用队列来处理。

• 初始化一个队列，将根节点加入到队列中
• 当队列不为空的时候，就将队列的元素出队，将最后一个元素加入到结果数组中
• 在元素出队列的时候，将元素的左右子节点分别加入到队列中
• 重复上面的第二三步，直至队列为空 ```javascript /**
  • Definition for a binary tree node.
  • function TreeNode(val) {
  • this.val = val;
  • this.left = this.right = null;
  • } / /*
  • @param {TreeNode} root
  • @return {number[]} */

// DFS的实现： var rightSideView = function(root) { if(!root) return [] let res = [] dfs(root, 0, res) return res };

function dfs(root, level, res){ if(root){ if(res.length === level){ res.push(root.val) }

    dfs(root.right, level+1, res)
    dfs(root.left, level+1, res)
}

}

// BFS的实现： var rightSideView = function(root) { if(!root) return [] let res = [] let queue = [root] while(queue.length > 0){ let len = queue.length

    while(len){
        let node = queue.shift()
        if(len === 1){
            res.push(node.val)
        }
        if(node.left){
            queue.push(node.left)
        }
        if(node.right){
            queue.push(node.right)
        }
        len--
    }
}
return res

};

**DFS复杂度分析：**
- 时间复杂度 : O(n)。其中n是二叉树的节点数，深度优先搜索最多访问每个结点一次，因此是线性复杂度。
- 空间复杂度 : O(n)。其中n是二叉树的节点数，最坏情况下，栈内会包含接近树高度的结点数量，占用 O(n) 的空间。
**BFS复杂度分析：**
- 时间复杂度 : O(n)。其中n是二叉树的节点数，每个节点最多进队列一次，出队列一次，因此广度优先搜索的复杂度为线性。
- 空间复杂度 : O(n)。其中n是二叉树的节点数，每个节点最多进队列一次，所以队列长度最大不不超过 n，所以这里的空间代价为 O(n)。
<a name="DuuM2"></a>
#### （8）完全二叉树的节点个数
给你一棵 **完全二叉树** 的根节点 `root` ，求出该树的节点个数。
[完全二叉树](https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin) 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 `h` 层，则该层包含 `1~ 2` 个节点。
**示例 1：**<br />![](https://cdn.nlark.com/yuque/0/2021/jpeg/1500604/1616318342325-054b6120-a9cf-47f8-8526-82faca2672c2.jpeg#height=302&id=Qx43Y&originHeight=302&originWidth=372&originalType=binary&ratio=1&rotation=0&showTitle=false&size=0&status=done&style=shadow&title=&width=372)
```javascript
输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

提示：

• 树中节点的数目范围是[0, 5 * 10]
• 0 <= Node.val <= 5 * 10
• 题目数据保证输入的树是 完全二叉树

进阶： 遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

对于这道题目，我们可以使用深度优先遍历或者广度优先遍历来计算二叉树的节点数。

1）深度优先遍历： 深度优先遍历就很简单了，题中传入的是二叉树，需要返回的是二叉树，所以可以直接进行递归计算二叉树的节点数：

• 如果子树为空节点数为 0
• 如果子树存在左子树或右子树则节点数+1，继续递归分别求左子树节点数和右子树节点数

复杂度分析：

• 时间复杂度：O(n)，其中n是二叉树的节点数，我们需要遍历一遍整个二叉树；
• 空间复杂度：O(h)，其中h是二叉树的高度，递归的时间复杂度为O(h)。

2）广度优先遍历： 广度优先遍历往往是初始化一个对来保存当前层的节点，在对当前层的节点进行操作。对于这题目，我们只需要在节点进入队列的时候，结果加一即可。

复杂度分析：

• 时间复杂度：O(n)，其中n是二叉树的节点数，我们需要遍历一遍整个二叉树；
• 空间复杂度：O(n)，其中n是队列的长度，我们需要将每一层都放在队列中。

3）二分法
上面的两种方法的时间复杂度都是O(n)，下面用二分法来解决，时间复杂度会降低。

我们知道，对于一个完全二叉树，它的所有子树都是完全二叉树，有的子树是满二叉树，满二叉树的的节点个数计算公式如下：2-1，其中h为当前树的高度。

那什么情况下就是满二叉树呢，我们知道，二叉树中有个树的深度的概念，指的就是根节点到这个节点所经历的边的个数， 所以我们只需要判断左右子树的高度手否相等来判断当前树是不是满二叉树。

如果不是满二叉树，那就是规模小一点的完全二叉树，就进行递归处理。

复杂度分析：

• 时间复杂度：每次递归调用对应了一层树高，调用logN次，每次调用计算完全二叉树的高度需要O(logN)，所以时间复杂度为O(logN)
• 空间复杂度：O(1)，我们只需要维护有限的额外空间。

广度优先遍历：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    if(!root){
        return 0
    }
    let queue = [root]
    let res = 1
    while(queue.length){
        let node = queue.shift()
        if(node.left){
            queue.push(node.left)
            res++
        }
        if(node.right){
            queue.push(node.right)
            res++
        }
    }
    return res
};

深度优先遍历：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    if(!root){
        return 0
    }
    return 1 + countNodes(root.left) + countNodes(root.right)
}

二分法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    if(!root){
        return 0
    }
    let leftHeight = 0, rightHeight = 0
    let leftNode = root, rightNode = root
    while(leftNode){
        leftHeight++
        leftNode = leftNode.left
    }
    while(rightNode){
        rightHeight++
        rightNode = rightNode.right
    }
    if(leftHeight === rightHeight){
        return 2 ** leftHeight - 1
    }
    return 1 + countNodes(root.left) + countNodes(root.right)
};

（9）左叶子之和

计算给定二叉树的所有左叶子之和。示例：

3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

对于这道题目，我们可以对二叉树进行层序遍历， 初始化一个对来queue来保存当前层的元素，遍历队列中的元素，如果该节点的左子树不存在左右子树，说明它是一个左叶子节点，将其加在结果上。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {
    if(!root) return 0
    let res = 0
    const queue = [root]
    while(queue.length){
        const cur = queue.shift()
        if(cur.left){
            if(!cur.left.left && !cur.left.right){
                res += cur.left.val
            }
            queue.push(cur.left)
        }
        if(cur.right){
            queue.push(cur.right)
        }
    }
    return res
};

复杂度分析：

• 时间复杂度：O(n)，最坏的情况下，也就是二叉树只有右子树，而形成一个链表的时候，我们需要遍历完整个二叉树，时间复杂度就是 O(n)；
• 空间复杂度：O(n)，其中n表示队列的长度，这个长度永远小于等于二叉树的节点的数量。

  （10）找树左下角的值

  给定一个二叉树，在树的最后一行找到最左边的值。
  示例 1:

  输入:
    2
   / \
  1   3
  输出:1

  示例 2:

  输入:
        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7
  输出:7

  注意: 您可以假设树（即给定的根节点）不为 NULL。

这里可以对二叉树进行层序遍历，而层序遍历就是基于广度优先遍历的。

在遍历的过程中，我们初始化一个队列来保存当前层的节点，这个过程中，需要先将根节点的右子节点加入到队列中，再将其左子节点加入到队列中。

这个过程中，将对列元素出队，并加入到res数组中，这样数组的最后一个值就是二叉树左下角的值。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
    const queue = [root]
    let res = []
    while(queue.length){
        const node = queue.shift()
        res.push(node.val)
        node.right && queue.push(node.right)
        node.left && queue.push(node.left)
    }
    return res[res.length - 1]
};

复杂度分析：

• 时间复杂度：O(n)，其中n是二叉树的节点数，我们需要遍历整棵树；
• 空间复杂度：O(n)，其中n是二叉树的高度，我们需要初始化一个数组来保存二叉树的所有节点；

  （11）最大二叉树

  给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：

1. 二叉树的根是数组 nums 中的最大元素。
2. 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
3. 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。

返回有给定数组 nums 构建的 最大二叉树。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• nums 中的所有整数 互不相同

这道题目我们直接使用递归来实现：

• 首先获取到数组中最大的值，来作为当前的根节点
• 分别获取数组中最大值的左边的数组元素和右边的数组元素

• 使用两个数组分别进行递归构建二叉树的左右子树

  /**
  * Definition for a binary tree node.
  * function TreeNode(val, left, right) {
  *     this.val = (val===undefined ? 0 : val)
  *     this.left = (left===undefined ? null : left)
  *     this.right = (right===undefined ? null : right)
  * }
  */
  /**
  * @param {number[]} nums
  * @return {TreeNode}
  */
  var constructMaximumBinaryTree = function(nums) {
    if(nums.length === 0){
        return null
    }
    let max = Math.max(...nums)
    let root = new TreeNode(max)
    let leftArray = nums.slice(0, nums.indexOf(max))
    let rightArray = nums.slice(nums.indexOf(max) + 1)
    root.left = constructMaximumBinaryTree(leftArray)
    root.right = constructMaximumBinaryTree(rightArray)
    return root
  };

  复杂度分析：

• 时间复杂度：O(n)，一共递归了 n 次。每次递归寻找根节点时，需要遍历当前索引范围内所有元素找出最大值。一般情况下，每次遍历的复杂度为 O(logn)，总复杂度为 O(nlogn)。最坏的情况下，数组 nums 有序，总的复杂度为 O(n)

• 空间复杂度：O(n)。递归调用深度为 n。平均情况下，长度为 n 的数组递归调用深度为 O(logn)。

  （12）相同的树

  给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入:       1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
输出: true

示例 2:

输入:      1          1
          /           \
         2             2
        [1,2],     [1,null,2]
输出: false

示例 3:

输入:       1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
输出: false

我们只需要进行递归遍历两个树对应的节点，看看是否一致，一致的话就直接返回false。这里使用的是深度优先遍历来进行遍历操作。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if(!p && !q){
        return true
    }
    if(p === null || q === null){
        return false
    }
    if(p.val !== q.val){
        return false
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

复杂度分析：

• 时间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。
• 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。

  （13）出现次数最多的子树元素和

  给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
示例 1：

输入:
  5
 /  \
2   -3
返回 [2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。

示例 2：

输入：
  5
 /  \
2   -5
返回 [2]，只有 2 出现两次，-5 只出现 1 次。

提示： 假设任意子树元素和均可以用 32 位有符号整数表示。

这道题和二叉树的众数那道题是一样的思路：

• 首先，先遍历出一次树， 求所有节点的子树和
• 在遍历的过程中，使用map来记录每个元素出现的次数

• 遍历完成之后，遍历map，找出次数最多的和，放在res中即可

  /**
  * Definition for a binary tree node.
  * function TreeNode(val) {
  *     this.val = val;
  *     this.left = this.right = null;
  * }
  */
  /**
  * @param {TreeNode} root
  * @return {number[]}
  */
  var findFrequentTreeSum = function(root) {
    let map = {}, res = [], max = 0
    const calcuSum = (root) => {
        if(!root){
            return 0
        }
        let left = calcuSum(root.left)
        let right = calcuSum(root.right)
        let sum = left + right + root.val
        // 将当前节点赋值为其所有子节点的和，方便后面进行计算
        root.val = sum
        map[sum] ? map[sum] += 1 : map[sum] = 1
        return root.val
    }
    calcuSum(root)
    for(let key in map){
        if(map[key] === max){
            res.push(key)
        }
        if(map[key] > max){
            max = map[key]
            res = [key]
        }
    }
    return res
  };

  复杂度分析：

• 时间复杂度：O(n)，其中n是这棵树的节点数量，我们需要遍历整棵树，来求每个节点的子树和。

• 空间复杂度：O(n)，其中n是这棵树的节点数量，这里需要的是递归的栈空间的空间代价。

  （14）二叉树最大宽度

  给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree） 结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例 1:

输入:
           1
         /   \
        3     2
       / \     \  
      5   3     9 
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2:

输入:
          1
         /  
        3    
       / \       
      5   3     
输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:

输入:
          1
         / \
        3   2 
       /        
      5      
输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

示例 4：

输入:
          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

注意: 答案在32位有符号整数的表示范围内。

这个题目，我们可以一层一层对二叉树进行遍历，初始化一个队列来保存这一层的节点，这个队列中保存着当前节点的节点值和索引值。

我们知道，一个节点的左子树的索引值是其索引值的两倍，即：left = index* 2，右子树的索引值是其索引值的两倍加一，即：right = index * 2 + 1。所以每层的宽度就是：right - left + 1，这样每一层的宽度值就求出来了，最大值也就自然而然的求出来了。

除此之外，我们还要考虑一种情况，就是二叉树深度特别深的时候，索引有可能就超出了数字的有效值。题目最后标明了：答案在32位有符号整数的表示范围内。也就是说最终答案那个最大宽度是不会超过32位有符号整数的。上面的想法是空节点也标注了索引，假如层数很多，但每层只有一个右节点的用例，空节点也计数就不行了，因为并没有限制层数。我们可以让同一层节点的索引先减去此层第一个节点的索引再来计算子节点的索引，这样每一层的索引都是从0开始的，从而解决数字大的问题。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var widthOfBinaryTree = function(root) {
    if(!root){
        return 0
    }
    const nodes = [{node: root, index: 0}]
    let res = 0
    while(nodes.length){
        let len = nodes.length
        const start = nodes[0].index
        const end = nodes[len - 1].index
        res = Math.max(res, end - start + 1)
        while(len--){
            let {node, index} = nodes.shift()
            index -= start
            node.left && nodes.push({ node: node.left, index: index * 2 })
            node.right && nodes.push({ node: node.right, index: index * 2 + 1 })
        }
    }
    return res  
};

复杂度分析：

• 时间复杂度：O(n)，其中n是二叉树的节点数，我们需要遍历完整个二叉树；

• 空间复杂度：O(n)，其中n是nodes栈的长度。

  （15）二叉树的最大深度

  给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例：给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

  递归实现：
  递归二叉树的节点，获取左子树和右子树的最大深度，比较后，返回最大深度，具体步骤如下：

• 判断二叉树是否为空，空的直接返回 0，结束，非空二叉树继续

• 分别递归计算左右子树的最大深度

• 根据返回两者的两者数字，比较后的返回二叉树的最大深度

  /**
  * Definition for a binary tree node.
  * function TreeNode(val) {
  *     this.val = val;
  *     this.left = this.right = null;
  * }
  */
  /**
  * @param {TreeNode} root
  * @return {number}
  */
  var maxDepth = function(root) {
    if(!root){
        return 0;
    }else{
        var leftDepth = maxDepth(root.left)
        var rightDepth = maxDepth(root.right)
        return Math.max(leftDepth,rightDepth)+1
    }
  };

  复杂度分析：

• 时间复杂度： O(n)：通过递归的方式查询了树的所有子节点。查询花费 O(n) 的时间。

• 空间复杂度： O(n)：每次递归都需要创建新的临时空间，空间复杂度 O(n)。

  （16）二叉树的最小深度

  给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。示例 1：
  

  输入：root = [3,9,20,null,null,15,7]
  输出：2

  示例 2：

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

  提示：

• 树中节点数的范围在 [0, 105] 内

• -1000 <= Node.val <= 1000