题目一览图

树 - 图1

零、树的概述

【树的定义】
【树】是一种非线性数据结构。树结构的基本单位是节点。节点之间的链接，称为分支 branch 。节点与分支形成树状，结构的开端，称为根 root，或根结点。根节点之外的节点，称为子节点 child。没有链接到其他子节点的节点，称为叶节点 leaf。
image.png

【树】**不仅是基本的数据结构，也是理解【递归】的重要工具。以菲波那切数列为例子，【递归】过程可以绘制为下图，动画过程可以使用这网站查看。
image.png

一、二叉树

类型概述

【二叉树概述】
【二叉树 Binary tree 】是树形结构的一个重要类型。【二叉树】的特点是每个节点最多只有两棵子树，即【左子树】和【右子树】。其代码定义是：

  1. struct TreeNode {
  2.     int val;
  3.     TreeNode *left;
  4.     TreeNode *right;
  5.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  6. };
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}


【二叉树分类】**

  • 【满二叉树】如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

image.png

  • 【完全二叉树】在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

image.png

  • 【二叉搜索树】是一棵有序树，简单来说就是左节点小，右节点大。具体来说，树里的数值满足：
    • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    • 它的左、右子树也分别为二叉排序树。

image.png

  • 【平衡二叉树】又称 AVL 树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

【二叉树遍历】
【树的遍历】有两种基本形式，以及四种延伸形式：

  • 【深度优先遍历 DFS 】先一直深入，到子节点再往回走。
    • 【前序遍历】节点 - 左 - 右
    • 【中序遍历】左 - 节点 - 右
    • 【后序遍历】左 - 右 - 节点
  • 【广度优先遍历 BFS 】一层一层遍历。
    • 【层序遍历】

其中常见的【前序遍历】、【中序遍历】以及【后序遍历】，区别就是在什么时候做节点数据的处理。三种遍历方法都要掌握【递归】和【迭代】两种写法。

递归 DFS 模板

这三种遍历算法的【递归】方式都源于【DFS】，所以在此可以先给一个统一的模板。

const dfs = (root)=>{
    if( 满足特定条件 ){ 返回操作 }
  // 前序在这操作
  dfs(root.left);
  // 中序在这操作
  dfs(root.right);
  // 后序在这操作
}

「前序遍历」模板

【前序**遍历**】是先处理节点数据，然后再遍历左右子树。

// 递归版
var preorderTraversal = function(root) {
    const res = [];
    const preorder = (node)=>{
        if( !node ) return;
        res.push(node.val);
        preorder(node.left);
        preorder(node.right);
    }
    preorder(root);
    return res;
};

// 迭代版
var preorderTraversal = (root) => {
  const res = [], stack = [];
    let node = root;
  while (stack.length || node ) {
    while( node ){
        res.push(node.val);
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    node = node.right
  }
  return res;
};

「中序遍历」模板

【中序**遍历**】先处理左子树，然后处理节点数据，最后处理右子树。

// 递归版
var inorderTraversal = function(root) {
    const res = [];
    const inorder = (node)=>{
        if( !node ) return;
        preorder(node.left);
          res.push(node.val);
        preorder(node.right);
    }
    inorder(root);
    return res;
};

// 迭代版
var inorderTraversal = (root) => {
  const res = [], stack = [];
  let node = root;

  while (stack.length || node ) {
    if( node ){
        stack.push(node);
      node = node.left;
    }else{
      node = stack.pop();
        res.push(node.val);
      node = node.right;
    }
  }
  return res;
};

**

「后序遍历」模板

【后序**遍历**】先处理左右子树，然后处理节点数据。不过后序遍历迭代版比较复杂，但是把它理解为倒叙的翻转版，就会很顺利得到解法。

// 递归版
var postorderTraversal = function(root) {
    const res = [];
    const postorder = (node)=>{
        if( !node ) return;
        preorder(node.left);
        preorder(node.right);
          res.push(node.val);
    }
    postorder(root);
    return res;
};

// 迭代版
var postorderTraversal = (root) => {
  const res = [], stack = [];
  let node = root;

  while (stack.length || node ) {
    if( node.left ){
        stack.push(node);
      node = node.left;
    }else if( node.right ){
        stack.push(node);
      node = node.right;
    }else{
      res.push(node.val);
      node = stack.pop();
      // 只可能存在于边界
      if (node && node.left) node.left = null
      else if (node && node.right) node.right = null
    }
  }
  return res;
};
// 迭代版（倒叙）
var postorderTraversal = (root) => {
  let res = [], stack = []
  while (root || stack.length) {
    res.unshift(root.val)
    if (root.left) stack.push(root.left)
    if (root.right) stack.push(root.right)
    root = stack.pop()
  }
  return res;
};

「层序遍历」模板

【层序**遍历**】一般借助【队列】，一层层入，一层层出，基本代码如下：

var levelOrder = function(root) {
    const queue = [] , res = [];
    if( root ) queue.push(root);
    while( queue.length ){
        res.push([]);
        let k = queue.length;
        while( k-->0 ){
            const node = queue.shift();
            res[res.length-1].push(node.val);
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
    }
    return res;
};

题型一 | 遍历 - 前序遍历

题型串联

1 相同的树

【概述】前序遍历
【题目描述**】
给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
【题目分析**】只有父节点相同，两棵树才可能相同，所以使用【前序遍历】先判断父节点。
【边界条件**】**

  • 左右树 q 和 p 同时不存在，判定为相同。
  • 左右树 q 和 p 仅有一个存在，判定为不同。

【前序处理**】**

  • 【节点操作】两个节点值是否相同，不同的话直接退出。
  • 【左递归】对比p.left q.left。

  • 【右递归】对比p.right q.right。

    var isSameTree = function(p, q) {
if( !q && !p ) return true;
if( !q || !p ) return false;
return q.val === p.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
};

    2 对称二叉树

    【概述】前序遍历
    【题目描述**】
    给定一个二叉树，检查它是否是镜像对称的。
    【题目分析**】核心在于对【镜像】的理解。
    【镜像**】根节点相同，左右子树对称。也就是最左对最右，次左对次右，以此类推。
    【边界条件**】

  • 左右树 q 和 p 同时不存在，判定为相同。

  • 左右树 q 和 p 仅有一个存在，判定为不同。

【前序处理**】**

  • 【节点操作】两个节点值是否相同，不同的话直接退出。
  • 【左递归】对比l.left r.right。

  • 【右递归】对比l.right r.left。

    var isSymmetric = function(root) {
const isSym = (l,r)=>{
   if( !l && !r ) return true;
   if( !l || !r ) return false;
   return l.val === r.val && isSym(l.left,r.right) && isSym(l.right,r.left);
}
return isSym(root,root);
};

    3 路径总和

    【概述】前序遍历
    【题目描述**】
    给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
    【题目示例**】

                           5
        / \
       4   8
      /   / \
     11  13  4
    /  \      \
   7    2      1

    【题目分析**】求和的顺序是从上到下，需要先加上根节点，再计算两子树路径和，所以使用【前序遍历】。
    【边界条件】**

  • 左右树 q 和 p 同时不存在，说明到底部，判断路径和是否符合。

  • 节点为空，说明它经历过【左右树 q 和 p 同时不存在】的判断，所以没有符合结果。

【前序处理**】**

  • 【节点操作】节点值是否等于 sum 。
  • 【左递归】判断root.left 是否满足路径和 sum-root.val。

  • 【右递归】判断root.right 是否满足路径和 sum-root.val。

    var hasPathSum = function(root, sum) {
if( !root ) return false;
if( !root.right && !root.left) return sum === root.val;
return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
};

    4 路径总和 II

    【概述】前序遍历
    【题目描述**】
    给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
    【题目示例**】

             5
        / \
       4   8
      /   / \
     11  13  4
    /  \    / \
   7    2  5   1

    【题目分析**】本题与【路径之和】一样，只是多了路径输出，也就是多个回溯算法。
    【边界条件】**

  • 左右树 q 和 p 同时不存在，说明到底部，判断路径和是否符合。

  • 节点为空，说明它经历过【左右树 q 和 p 同时不存在】的判断，所以没有符合结果。

【前序处理**】**

  • 【节点操作】节点值是否等于 sum ，如果满足压入路径。
  • 【左递归】判断root.left 是否满足路径和 sum-root.val。

  • 【右递归】判断root.right 是否满足路径和 sum-root.val。

    var pathSum = function(root, sum) {
const res = [];

const backtrack = (node,sum,path)=>{
   if( !node ) return;
   path.push(node.val)
   if(!node.left && !node.right) if( node.val === sum ) res.push([...path]);
   if(node.left) backtrack(node.left,sum-node.val,path);
   if(node.right) backtrack(node.right,sum-node.val,path);
   path.pop();
}

backtrack(root,sum,[]);
return res;
};

    5 求根到叶子节点数字之和

    【概述】前序遍历
    【题目描述**】
    给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
    例如，从根到叶子节点路径 1->2->3 代表数字 123。计算从根到叶子节点生成的所有数字之和。
    【题目示例**】

                           5
        / \
       4   8
      /   / \
     11  13  4
    /  \      \
   7    2      1

    【题目分析**】本题本质与【路径之和】一样，只是常规求和加上十进制权重，即 sum * 10 + node.val 。也就是说第 1 层的数乘以 10^0 , 第 2 层的数乘以 10^1 , 第 3 层的数乘以 10^2 。
    【边界条件】**

  • 左右树 q 和 p 同时不存在，说明到底部，返回求和。

  • 节点为空，说明它经历过【左右树 q 和 p 同时不存在】的判断，所以没有符合结果。

【前序处理**】**

  • 【节点操作】节点值乘以十进制权重，并加进 sum 中 。
  • 【左递归】计算左子树数字之和。
  • 【右递归】计算右子树数字之和。

  • 最后返回中左右三值相加。

    var sumNumbers = function(root) {
const dfs = (node,sum)=>{
   if(node===null) return 0;
   sum = sum * 10 + node.val;
   if(!node.left&&!node.right) return sum;
   return dfs(node.left,sum) + dfs(node.right,sum);
}
return dfs(root,0);
};

    题型一 | 遍历 - 中序遍历

    题型串联

    1 验证二叉搜索树

    【概述】中序遍历
    【题目描述**】
    给定一个二叉树，判断其是否是一个有效的二叉搜索树。
    【题目分析**】本题涉及【二叉搜索树】，该树的最大特色是【中序遍历】为递增数组。
    【边界条件**】**

  • 节点 root 不存在，说明已经经历种种判断，达到树的底端，返回 true 。

【中序处理**】**

  • 【左递归】判断左子树 root.left 是否为【二叉搜索树】，只有返回 true 的时候，才继续操作。
  • 【节点操作】判断当前节点是否大于前一个节点 pre ，如果是的话，说明当前中序遍历为递增，符合二叉搜索树的条件。

  • 【右递归】判断右子树 root.right 是否为【二叉搜索树】。

    var isValidBST = function(root) {
let pre = Number.MIN_SAFE_INTEGER;
const isValid = (root)=>{
   if( !root ) return true;
   if( !isValid(root.left)) return false;
   if( root.val <= pre ) return false;
   pre = root.val;
   return isValid(root.right)
}
return isValid(root);
};

    2 恢复二叉搜索树

    【概述】中序遍历
    【题目描述**】
    给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
    【题目分析**】本题涉及【二叉搜索树】，该树的最大特色是【中序遍历】为递增数组。题目要求找到两个【错位点】，所以用【中序遍历】过一遍树，将两个跳脱的节点找到，最后交换即可。
    【边界条件**】**

  • 节点 root 不存在，说明已经达到树的底端 。

【中序处理**】**

  • 【左递归】判断左子树 root.left 是否为【二叉搜索树】。
  • 【节点操作】判断当前节点是否大于前一个节点 pre ，如果不是说明遇到【错位点】，记录下来（两次）。

  • 【右递归】判断右子树 root.right 是否为【二叉搜索树】。

    var recoverTree = function(root) {
let pre = new TreeNode(Number.MIN_SAFE_INTEGER) , p1 = p2 = null;
const inorder = (node)=>{
   if( !node ) return;
   inorder(node.left);
   if( pre.val >= node.val && !p1) p1 = pre;
   if( pre.val >= node.val && p1) p2 = node;
   pre = node;
   inorder(node.right);
}
inorder(root);
const tmp = p1.val;
p1.val = p2.val;
p2.val = tmp;
return root;
};

    题型一 | 遍历 - 后序遍历

    题型串联

    1 二叉树的最大深度

    【概述】后序遍历
    【题目描述**】
    给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
    【题目分析**】当前节点高度需要先知道左右子树的高度才能计算，所以是【后序遍历】。
    【边界条件**】**

  • 节点 root 不存在，说明已经达到树的底端，高度为 0 。

【后序处理**】**

  • 【左递归】计算左子树高度。
  • 【右递归】计算右子树高度。

  • 【节点操作】max(左子树高度 , 右子树高度 )+ 1。

    var maxDepth = function(root) {
if(!root) return 0;
else return Math.max( maxDepth(root.left), maxDepth(root.right)) + 1;
};

    2 二叉树的最小深度

    【概述】后序遍历
    【题目描述**】
    给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
    【题目示例**】

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

    【题目分析**】
    【边界条件**】

  • 节点 root 不存在，说明已经达到树的底端，高度差为 0 。

【后序处理**】**

  • 【左递归】计算左子树深度。
  • 【右递归】计算右子树深度。

  • 【节点操作】

    • 如果两子树都有，深度就是左右子树深度最大值加一 。
    • 如果两子树只有一个，深度就是有的那个子树深度加一 。
      var minDepth = function(root) {
if(!root) return 0;
if(!root.left&&!root.right) return 1;
const l = minDepth(root.left) , r = minDepth(root.right);
if( !root.right || !root.left ) return left + right + 1;
return Math.min(left,right)+1;
};

      3 平衡二叉树

      【概述】后序遍历
      【题目描述**】**
      给定一个二叉树，判断它是否是高度平衡的二叉树。
      本题中，一棵高度平衡二叉树定义为：

  • 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1

【题目分析**】本题本质是计算高度差，跟【二叉树的最大深度】一样是【后序遍历】。
【边界条件**】

  • 节点 root 不存在，说明已经达到树的底端，高度差为 0 。

【后序处理**】**

  • 【左递归】计算左子树高度。
  • 【右递归】计算右子树高度。

  • 【节点操作】

    • 如果左右高度差有一是 -1 ，说明有大于高度差大于 1 的子树，所以结果也是 -1 。
    • 左右高度差的差大于 1 ，返回 -1 。

    • 返回最大高度差 + 1 。

      var isBalanced = function (root) {
const height = (node)=>{
if( !node ) return 0;
const lH = height(node.left);
const rH = height(node.right);

if( lH === -1 || rH === -1 || Math.abs(rH-lH)>1) return -1;
else return Math.max(rH,lH)+1;
}
return height(root)>=0; 
};

      4 二叉树展开为链表

      【概述】后序遍历
      【题目描述**】
      给定一个二叉树，原地将它展开为一个单链表。
      【题目示例**】

      1
/ \
2   5
/ \   \
3   4   6 
1
\
2
\
3
\
4
\
5
 \
  6

      【题目分析**】本题重点考察递归思维，只关注一个节点怎么展开，然后推广全树。
      【边界条件**】

  • 节点 root 不存在，说明已经达到树的底端，退出递归 。

【后序处理**】**

  • 【左递归】展开后的左子树。
  • 【右递归】展开后的右子树。

  • 【节点操作】

    • 【展开后的左子树】放至节点右侧，左侧接空。
    • 【展开后的右子树】接在【展开后的左子树】最后的右节点。 ```javascript var flatten = function(root) { if( !root ) return ;

    flatten(root.left); flatten(root.right);

    const left = root.left , right = root.right;

    root.left = null; root.right = left;

    let p = root; while( p.right ) p = p.right; p.right = right; };

    <a name="FS4rW"></a>
### 题型一 | 遍历 - 层序遍历
<a name="bwQj2"></a>
#### 题型串联
<a name="gWUD0"></a>
#### 1 [二叉树的层序遍历 II](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)
**【概述】层序遍历**<br />**【题目描述****】**<br />给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）<br />**【题目分析****】**本题与普通层序遍历没有区别，只是输出路径的时候反着输出。**
```javascript
var levelOrderBottom = function(root) {
const queue = [] , res = [] ;
if( root ) queue.push(root);
while( queue.length ){
   res.unshift([]);
   let k = queue.length;
   while( k-- >0 ){
       const node = queue.shift();
       res[0].push(node.val);
       if(node.left) queue.push(node.left);
       if(node.right) queue.push(node.right);
   }
}
return res;
};

    2 二叉树的右视图

    【概述】层序遍历
    【题目描述**】
    给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
    【题目分析**】本题与普通层序遍历区别不大，就是输出每一层的最后一个。

    var rightSideView = function(root) {
const queue = [] , res = [];
if( root ) queue.push(root);
while(queue.length){
   let k = queue.length;
   while( k-- > 0){
       const node = queue.shift();
       if(k===0) res.push(node.val);
       if(node.left) queue.push(node.left);
       if(node.right) queue.push(node.right);
   }
}
return res;
};

    3 二叉树的层平均值

    【概述】层序遍历
    【题目描述**】
    给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
    【题目分析**】本题与普通层序遍历区别不大，就是输出每层的平均值。

    var averageOfLevels = function(root) {
const queue = [] , res = [];
if( root ) queue.push(root);
while(queue.length){
   const len = queue.length;
   let k = len , sum = 0;
   while( k-- > 0){
       const node = queue.shift();
       sum += node.val;
       if(node.left) queue.push(node.left);
       if(node.right) queue.push(node.right);
   }
   res.push(sum/len);
} 
return res;
};

    4 在每个树行中找最大值

    【概述】层序遍历
    【题目描述**】
    给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
    【题目分析**】本题与普通层序遍历区别不大，就是输出每层的最大值。

    var largestValues = function(root) {
const queue = [] , res = [];
if( root ) queue.push(root);
while(queue.length){
   let k = queue.length , max = Number.MIN_SAFE_INTEGER;
   while( k-- > 0){
       const node = queue.shift();
       max = Math.max(node.val,max);
       if(node.left) queue.push(node.left);
       if(node.right) queue.push(node.right);
   }
   res.push(max);
} 
return res;
};

    5 填充每个节点的下一个右侧节点指针

    【概述】层序遍历
    【题目描述**】
    给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
    【题目分析**】本题使用层序遍历区，对每一层的元素进行连接，就层头尾操作略有区分。

    var connect = function(root) {
const queue = [];
if( root ) queue.push(root);
while(queue.length){
   let k = queue.length - 1 ;
   let pre = queue.shift();
   if(pre.left) queue.push(pre.left);
   if(pre.right) queue.push(pre.right);
   while( k-- > 0){
       const node = queue.shift();
       pre = pre.next = node;
       if(node.left) queue.push(node.left);
       if(node.right) queue.push(node.right);
   }
   pre.next = null;
}
return root;
};

    6 填充每个节点的下一个右侧节点指针 II

    【概述】层序遍历
    【题目描述**】
    给定一个二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
    【题目分析**】本题使用层序遍历区，如果从层序考虑，与【填充每个节点的下一个右侧节点指针】完全一致。

    var connect = function(root) {
const queue = [];
if( root ) queue.push(root);
while(queue.length){
   let k = queue.length - 1 ;
   let pre = queue.shift();
   if(pre.left) queue.push(pre.left);
   if(pre.right) queue.push(pre.right);
   while( k-- > 0){
       const node = queue.shift();
       pre = pre.next = node;
       if(node.left) queue.push(node.left);
       if(node.right) queue.push(node.right);
   }
   pre.next = null;
}
return root;
};

    7 二叉树的锯齿形层序遍历

    【概述】层序遍历
    【题目描述**】
    给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
    【题目分析**】本题与普通层序遍历区别不大，就是路径输出的时候要判断奇偶，【奇数】放前面 【偶数】放后面。

    var zigzagLevelOrder = function(root) {
const queue = [] , res = [];
if( root ) queue.push(root);
while(queue.length){
   res.push([]);
   let k = queue.length;
   while( k-- > 0){
       const node = queue.shift();
       if( res.length % 2) res[res.length-1].push(node.val);
       else res[res.length-1].unshift(node.val);
       if(node.left) queue.push(node.left);
       if(node.right) queue.push(node.right);
   }
} 
return res;
};

    8 N 叉树的层序遍历

    【概述】层序遍历
    【题目描述**】
    给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
    【题目分析**】本题与普通层序遍历区别不大，只是孩子多了需要遍历而已。

    var levelOrder = function(root) {
const queue = [] , res = [];
if( root ) queue.push(root);
while(queue.length){
   res.push([]);
   let k = queue.length;
   while( k-- > 0){
       const node = queue.shift();
       res[res.length-1].push(node.val);
       for( let child of node.children ) queue.push(child);
   }
} 
return res;
};

    题型二 | 树的构建

    题型串联

    1 将有序数组转换为二叉搜索树

    【概述】树的创建
    【题目描述**】
    将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
    【题目分析**】本题涉及【二叉搜索树】，该树的最大特色是【中序遍历】为递增数组。只要保证【根节点】大于左侧，小于右侧即可。为了保证高度平衡，我们选择数组 nums 中点作为根节点。
    【递归**】 **

  • 【函数定义】build(l,r) 表示用 nums[l ... r] 构造的平衡二叉树。

  • 【返回值定义】root 。构造完成的平衡二叉树的根节点。

  • 【构造过程】

    • 【跳出条件】l>r 。
    • 【根节点】用中值构造，new TreeNode(nums[mid]) 。
    • 【左子树】build(l,mid-1)，即用 nums[l ... mid-1] 构造的平衡二叉树。
    • 【右子树】build(mid+1 , r)，即用nums[mid+1 ... r] 构造的平衡二叉树。
      var sortedArrayToBST = function(nums) {
if(!nums.length) return null;
const n = nums.length;
const build = (l,r)=>{
if(l>r) return null;
const mid = l+r >>1;
const root = new TreeNode(nums[mid]);
root.left = build(l,mid-1);
root.right = build(mid+1,r);
return root;
}
return build(0,n-1);
};

      2 有序链表转换二叉搜索树

      【概述】树的创建
      【题目描述**】
      给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
      【题目分析**】

  • 本题涉及【二叉搜索树】，该树的最大特色是【中序遍历】为递增数组。

  • 本题与【将有序数组转换为二叉搜索树】类似，区别在于用的是【链表】。【链表】是递增的，所以我们用【中序遍历】依次创建即可。

【递归**】 **

  • 【函数定义】build(l,r) 表示用 l ... r 构造的平衡二叉树。
  • 【返回值定义】root 。构造完成的平衡二叉树的根节点。

  • 【构造过程】

    • 【跳出条件】l>r 。
    • 【左子树】build(l,mid-1)，即用 nums[l ... mid-1] 构造的平衡二叉树。
    • 【右子树】build(mid+1 , r)，即用nums[mid+1 ... r] 构造的平衡二叉树。
    • 先递归【左子树】 达到最左（最小）节点位置，用链表第一个元素创建【根节点】，然后再接上左右子树。 ```javascript var sortedListToBST = function(head) { if(!head) return null; let len = 0 , p = head; while(p) len++ , p = p.next;

    const build = (start , end )=>{ if(start>end) return null; const mid = start + end >> 1; const left = build(start,mid-1); const root = new TreeNode(head.val); head = head.next; root.left = left; root.right = build(mid+1,end); return root; } return build(0,len-1); }; ```

    3 不同的二叉搜索树 II

    【概述】树的创建
    【题目描述**】
    给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
    【题目分析**】本题涉及【二叉搜索树】，该树的最大特色是【中序遍历】为递增数组。只要保证【根节点】大于左侧，小于右侧即可。本题与【将有序数组转换为二叉搜索树】类似，区别在于选择不同的根节点，生成一个树的集合。
    【递归**】 **

  • 【函数定义】build(l,r) 表示用 l ... r 构造的平衡二叉树。

  • 【返回值定义】rootList ，构造完成的平衡二叉树的根节点的所有可能。

  • 【构造过程】

    • 【跳出条件】l>r ，返回 [null] 表示不存在（为了之后的遍历）
    • 【根节点】从 1 ... n 遍历，分别创建 new TreeNode(i) 。
    • 【左子树】build(l,i-1)，递归构建左子树，并拿到左子树所有可能的根结点列表leftRootList。
    • 【右子树】build(mid+1 , r)，递归构建右子树，并拿到右子树所有可能的根结点列表rightRootList。
      var generateTrees = function(n) {
const build = (l,r)=>{
if( l > r ) return [null];
const rootList = [];
for( let i = l ; i <= r ; i++){
    const leftRootList = build(l,i-1) , rightRootList = build(i+1,r);
    for(let lNode of leftRootList ){
        for(let rNode of rightRootList ){
            const tmp = new TreeNode(i);
            tmp.left = lNode , tmp.right = rNode;
            rootList.push(tmp);
        }
    }
}
return rootList;
}
if (n === 0) return [];
return build(1, n);
};

      4 不同的二叉搜索树

      【概述】树的创建
      【题目描述**】
      给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
      【题目分析**】

  • 由于只用计算次数，所以本题属于【动态规划】，但是【不同的二叉搜索树 II】接近，故放在一起。

  • 本题难点在于如何找【转移方程】，其他部分较为简单。

【转移方程**】**

  • 以 [1,2,3] 为例子
    • 1 为树根，左有 f(0) 种情况 ，右有 f(2) 种情况，一共是 f(0)*f(2) 种情况。
    • 2 为树根，左有 f(1) 种情况 ，右有 f(1) 种情况，一共是 f(1)*f(1) 种情况。
    • 3 为树根，左有 f(2) 种情况 ，右有 f(0) 种情况，一共是 f(2)*f(0) 种情况。
    • 此时 f(3) = f(2)f(0) + f(1)f(1) + f(0)f(2)
  • 同理，f(n) = f(n-1)f(0) + f(n-2)f(1) ... ``f(0)f(n-1) 。
var numTrees = function(n) {
    const dp = new Array(n+1).fill(0);
    dp[0] = 1;
    for( let i = 1 ; i<=n ; i++){
        dp[i] = 0;
        for( let j = 1 ; j<=i ; j++){
            dp[i] += dp[j-1] * dp[i-j];
        }
    }
    return dp[n];
};

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

【概述】树的创建
【题目描述**】
根据一棵树的前序遍历与中序遍历构造二叉树。
【题目分析**】

  • 【前序遍历】- [根节点][左子树][右子树]
  • 【中序遍历】- [左子树][根节点][右子树]
  • 【思路】顺序读取前序数组，定位每个子树的[根节点]。然后拿着[根节点]去中序数组确定左右子树的范围。

【递归**】 **

  • 【函数定义】build(preorder,preStart,preEnd,inorder,inStart,inEnd) 表示用 preorder[preStart,preEnd] 和 inorder[inStart,inEnd] 构造的平衡二叉树。
  • 【返回值定义】root ，构造完成的二叉树的根节点。

  • 【构造过程】

    • 【跳出条件】preStart > preEnd ，
    • 【根节点】 new TreeNode(preorder[preStart]) 。
    • 【左子树】
      • 左子树长度为 **len=index-inStart** ，其中 index 为根节点在中序数组的位置。
      • build(preorder,preStart+1,preStart+len,inorder,inStart,index-1)，递归构建左子树，返回根节点。
    • 【右子树】build(preorder,preStart+len+1,preEnd,inorder,index+1,inEnd)，递归构建右子树，返回根节点。
      const buildTree = (preorder, inorder) => {
const build = (preorder,preStart,preEnd,inorder,inStart,inEnd)=>{
if( preStart > preEnd ) return null;
let rootVal = preorder[preStart];
let index = 0;
for( let i = 0 ; i <= inEnd ; i++ ){
    if( inorder[i] === rootVal ){
        index = i;
        break;
    }
}
const root = new TreeNode(rootVal) , len = index - inStart ;
root.left = build(preorder,preStart+1, preStart + len,inorder,inStart,index-1);
root.right = build(preorder,preStart + len + 1 , preEnd , inorder , index + 1 , inEnd);
return root;
}
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
};

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

      【概述】树的创建
      【题目描述**】
      根据一棵树的中序遍历与后序遍历构造二叉树。
      【题目分析**】

  • 【后序遍历】- [左子树][右子树][根节点]

  • 【中序遍历】- [左子树][根节点][右子树]
  • 【思路】倒序读取前序数组，定位每个子树的[根节点]。然后拿着[根节点]去中序数组确定左右子树的范围。

【递归**】 **

  • 【函数定义】build(postorder,postStart,postEnd,inorder,inStart,inEnd) 表示用 postorder[postStart,postEnd] 和 inorder[inStart,inEnd] 构造的平衡二叉树。
  • 【返回值定义】root ，构造完成的二叉树的根节点。
  • 【构造过程】
    • 【跳出条件】postStart > postEnd ，
    • 【根节点】 new TreeNode(preorder[postEnd]) 。
    • 【左子树】
      • 左子树长度为 **len=index-inStart** ，其中 index 为根节点在中序数组的位置。
      • build(preorder,postStart,postEnd-len-1,inorder,inStart,index-1)，递归构建左子树，返回根节点。
    • 【右子树】build(preorder,postEnd-len,preEnd-1,inorder,index+1,inEnd)，递归构建右子树，返回根节点。
      var buildTree = function(inorder, postorder) {
const build = (postorder,postStart,postEnd,inorder,inStart,inEnd) =>{
if( postStart > postEnd ) return null; 
const rootVal = postorder[postEnd];
let index = 0;
for( let i = 0 ; i <= inEnd ; i++){
    if( inorder[i] === rootVal ) {
        index = i ; 
        break;
    }
}
const root = new TreeNode(rootVal) , len = inEnd - index;
root.left = build(postorder,postStart,postEnd-len-1,inorder,inStart,index-1);
root.right = build(postorder,postEnd-len,postEnd-1,inorder,index+1,inEnd);
return root;
}
return build(postorder,0,postorder.length-1,inorder,0,inorder.length-1);
};