全栈大前端

# 二叉树

  • 特性

  • 二叉树是指满足以下要求的树：

  1. 它可以没有根结点，作为一棵空树存在

  2. 如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树

二叉树不能被简单定义为每个结点的度都是2的树。普通的树并不会区分左子树和右子树，但在二叉树中，左右子树的位置是严格约定、不能交换的

# 满二叉树

叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点。上文中的图就是满二叉树。

# 完全二叉树

  • 特性

  1. 从第一层到倒数第二层，每一层都是满的，也就是说每一层的结点数都达到了当前层所能达到的最大值

  2. 最后一层的结点是从左到右连续排列的，不存在跳跃排列的情况（也就是说这一层的所有结点都集中排列在最左

堆其实就是一种完全二叉树，一般采用堆存储方式是数组

# 二叉搜索树

  • 特性
  1. 是一棵空树
  2. 是一棵由根结点、左子树、右子树组成的树，同时左子树和右子树都是二叉搜索树，且左子树上所有结点的数据域都小于等于根结点的数据域，右子树上所有结点的数据域都大于等于根结点的数据域

满足以上两个条件之一的二叉树，就是二叉搜索树。

BST-> 中序遍历是递增的

# 平衡二叉树（AVL 树）

  • 特性

是任意结点的左右子树高度差绝对值都不大于1的二叉搜索树。

# Trie 树

Google、百度一类的搜索引擎强大的关键词提示功能的背后，最基本的原理就 Trie 树，通过空间换时间，利用字符串的公共前缀，降低查询的时间以提高效率。除此之外，还有很多应用，比如：IP 路由中使用了 Trie 树的最长前缀匹配算法，利用转发表选择路径以及 IDE 中的智能提示等。

# B+ 树

我们知道，将索引存储在内容中，查询速度是比存储在磁盘中快的。但是当数据量很大的情况下，索引也随之变大。内存是有限的，我们不得不将索引存储在磁盘中。那么，如何提升从磁盘中读取的效率就成了工程上的关键之一。 大部分关系型数据库的索引，比如 MySQL、Oracle，都是用 B+ 树来实现的。B+ 树比起红黑树更适合构建存储在磁盘中的索引。B+ 树是一个多叉树，在相同个数的数据构建索引时，其高度要低于红黑树。当借助索引查询数据的时，读取 B+ 树索引，需要更少的磁盘 IO 次数。 一个 m 阶的 B 树满足如下特征：

每个节点中子节点的个数 k 满足 m > k > m/2，根节点的子节点个数可以不超过 m/2通过双向链表将叶子节点串联在一起，方便按区间查找m 叉树只存储索引，并不真正存储数据一般情况，根节点被存储在内存中，其他节点存储在磁盘中

# 树的遍历（前、中、后、层次）

  • 前序遍历（根->左->右）

对于二叉树中的任意一个节点，先打印该节点，然后是它的左子树，最后右子树

//递归法
var preorderTraversal =function(root,array=[]){
    if(root){
        //递归实现
        array.push(root.val);
        preorderTraversal(root.left,array)
        preorderTraversal(root.right,array)
    }
    return array;
}

//迭代法
var preorderTraversal = function(root) {
     // 用一个栈辅助完成迭代遍历
     const stack = [];
     // 结果数组
     const res = [];
     // 如果当前节点为空或者栈为空时结束循环
     while(root || stack.length>0) {
         while(root) {
             // 因为是前序遍历，所以根节点先存放到结果数组
             res.push(root.val);
             // 为了在我们走到左子树的底部时，能够回到根节点继续遍历右子树，因此，先将根节点存入栈中
             stack.push(root);
             // 继续遍历左子树，直到遍历到叶子节点
             root = root.left;
         }
         // 左子树遍历完了，我们需要遍历右子树了，首先我们先要从栈顶把最近的一个根节点弹出
         root = stack.pop();
         // 遍历弹出的这个根节点的右子树
         root = root.right;
     }
     return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
  • 中序遍历(左->根->右)

对于二叉树中的任意一个节点，先打印它的左子树，然后是该节点，最后右子树

//递归实现
var inorderTraversal= function(root,array=[]){
    if(root){
        inorderTraversal(root.left,array)
        array.push(root.val)
        inorderTraversal(root.right, array);
    }
    return array
}


//迭代法
const inorderTraversal=function(root,array=[]){
    //初始化数据
    const res =[]
    const stack=[]
    while(root||stack.length){
        while(root){
            stack.push(root);
            root=root.left
        }
        root= stack.pop();
        res.push(root.val)
        root=root.right
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
  • 后序遍历(左->右->根)

对于二叉树中的任意一个节点，先打印它的左子树，然后是右子树，最后该节点

    var postorderTraversal = function (root, array = []) {
      if (root) {
        postorderTraversal(root.left, array);
        postorderTraversal(root.right, array);
        array.push(root.val);
      }
      return array;
    };

//迭代法
const postorderTraversal=function(root){
    const res =[]
    const stack=[]
    while(root||stack.length){
        while(root){
            stack.push(root)
            res.unshift(root.val)
            root=root.right
        }
        root= stack.pop()
        root.left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
  • DFS(深度优先遍历)

一个分枝走到底

  • BFS(广度优先遍历)

逐层遍历

# 高频题

# 反转二叉树(简单) (opens new window)

  • 递归
  1. 从根节点开始，递归的对树进行遍历。
  2. 从叶子结点开始进行翻转。
  3. 左右子树都已经翻转后，交换两棵子树的位置即可完成全部的翻转。
    const invertTree =function (root){
        if(root === null){
            return null
        } 
        invertTree(root.left)
        invertTree(root.right)
        const temp=root.left
        root.left= root.right
        root.right =temp     
        return root
    }
//时间复杂度: O(n)
//空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13

# 相同的树(简单) (opens new window)

  • 深度优先搜索DFS
  1. 如果两棵树都为空,则它们相同返回true
  2. 如果两个二叉树中有一个为空，则它们不同返回false
  3. 如果两个二叉树都不为空,首先判断根节点是否相同,不同则返回false
  4. 如果两个二叉树的根节点相同，则分别递归判断其左右子树是否相同
const isSameTree =function(p,q){
    if(p ===null && q===null) 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))
//空间复杂度: O(min(m, n))
1
2
3
4
5
6
7
8
9

# 对称二叉树(简单) (opens new window)

  • 递归

先明确,所谓"对称",也就是两个树的根节点相同且

  1. 第一个树的左子树与第二个树的右子树镜像对称
  2. 第一个树的右子树与第二个树的左树镜像对称
const isSymmetric= function (root){
    if(root ===null){
        return true
    }
    return isEqual(root.left,root.right)
}
const isEqual = function (left,right)
{
    //递归终止条件
    if(left === null && right ===null) return true
    if(left === null || right === null )return false
    //比较左右子树的root 值以及左右子树 是否对称
    return left.val === right.val && isEqual(left.left, right.right)
    && isEqual(left.right,right.left)
}
//时间复杂度: O(n)
//空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 二叉树的最大深度(简单) (opens new window)

  • DFS 深度优先搜索

树的深度= 左右子树的最大深度+1

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

//时间复杂度: O(n)
//最坏空间复杂度: O(height), height 表示二叉树的高度
1
2
3
4
5
6
7
8
9
10
11
12
13
  • BFS 广度优先搜索

层序遍历时记录树的深度

const maxDepth = function(root) {
    //层数
    let depth = 0
    if (root === null) {
        return depth
    }
    const queue = [root]
    while (queue.length) {
        let len = queue.length
        while (len--) {
            const cur = queue.shift()
            cur.left && queue.push(cur.left)
            cur.right && queue.push(cur.right)
        }
        depth++
    }
    return depth
};

//时间复杂度: O(n)
//空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 二叉树的最小深度 (opens new window)

  • 递归DFS
  1. root 为空时，高度为 0
  2. root 的左右子树都为空时，高度为 1
  3. 如果左子树或者右子树为空时，返回另一棵子树的高度
  4. 否则返回两棵子树的高度最小值
const minDepth =function (root){
    if(root ===null) return 0
    if(root.left ===null && root.right ===null){
        return 1
    }
    if(root.left ===null){
        return 1 + minDepth(root.right)
    }
    if(root.right === null){
        return 1+minDepth(root.left)
    }
    return Math.min(minDepth(root.left),minDepth(root.right))+1
}   

//时间复杂度：O(n)
//空间复杂度：O(logn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 平衡二叉树(简单) (opens new window)

  • 平衡二叉树定义：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1
  1. 如果遍历完成，还没有高度差超过1的左右子树，则符合条件
  2. 判断左右子树高度差，超过1则返回false
  3. 递归左右子树
  4. 封装获取子树高度函数getHeight

const isBalanced =function (root){
        if(!root) return true
        if(Math.abs(getHeight(root.left) - getHeight(root.right))>1){
            return false
        }
        return isBalanced(root.left) && isBalanced(root.right)
        function getHeight(root){
            if(!root) return 0
            return Math.max(getHeight(root.left),getHeight(root.right))+1
        }   
}

//时间复杂度：O(n)
//空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 有序数组转换为二叉搜索树(简单) (opens new window)

  • 递归
  1. 二叉搜索树的中序遍历是升序的，本题中给出的数组刚好是升序的，相当于通过中序遍历恢复二叉搜索树
  2. 可以选择升序序列中的任意位置的元素作为根节点，该元素左边的升序序列构建左子树，右边的升序序列构建右子树
  3. 题目又要求高度平衡，所以我们需要选择升序序列的中间位置的元素作为根节点即可
const sortedArrayToBST =function (nums){

    const buildTree = (arr,left,right)=>{
        if(left > right){
            return null
        }
        let mid = Math.floor(left+(right -left)/2)
        let root = new TreeNode(arr[mid])
        root.left = buildTree(arr,left,mid-1)
        root.right = buildTree(arr,mid+1,right)
        return root
    }
    return buildTree(nums,0,nums.length-1)
}
// 时间复杂度O(n)
// 空间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 路径总和(简单) (opens new window)

  • 递归
  1. 处理边界，节点不存在时返回false
  2. 左右子树都不存在时代表是叶子节点，判断是否符合条件
  3. 递归左右子树时进行转换，看能否找到 targetSum -root.val 的路径
const hasPathSum =(root,targetSum){
    if(root === null){
        return false
    }
    if(root.left === null && root.right === null){
        return root.val === targetSum
    }
    return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val)
}

//时间复杂度: O(n)
//空间复杂度: O(H)，H 是树的高度
1
2
3
4
5
6
7
8
9
10
11
12
13

# 二叉树的直经(简单) (opens new window)

  • 递归dfs

一棵二叉树的直径长度是任意两个结点路径长度中的最大值 这条路径可能穿过也可能不穿过根结点

  • 两个公式
  1. 最长路径=左子树最长路径 +右子树最长路径 +1（根结点）
  2. 高度(最大深度) = 左右子树中的最大深度+1（根结点）
const diameterOfBinaryTree =function (root){
    let ans =1
    function depth(node）{
        if(node ===null) return 0
        let L =depth(node.left)
        let R =depth(node.right)
        ans =Math.max(ans,L+R+1)
        return Math.max(L,R)+1
    }
    depth(root)
    return ans -1
}
// 时间复杂度: O(n)
// 空间复杂度: O(H)，H 为二叉树的高度
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 合并二叉树(简单) (opens new window)

  • DFS递归

在 root1 上直接修改，将两个树对应的节点相加后，赋值给 root1，然后递归执行两个左右子树。

const mergeTrees = function(root1, root2) {
    return preOrder(root1,root2)
};

function preOrder(root1,root2){
    if(!root1 &&!root2) return null
    if(!root1) return root2
    if(!root2) return root1
    root1.val+=root2.val
    root1.left=preOrder(root1.left,root2.left)
    root1.right=preOrder(root1.right,root2.right)
    return root1
}

//时间复杂度: O(min(m,n))
//空间复杂度: O(min(m,n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 二叉搜索树的第k个节点(简单) (opens new window)

  1. 因为是搜索二叉树 先中序遍历 先右再中再左；
  2. 过程中看count是否等于k 是的话 res = node.val；return
const kthLargest =function(root,k){
    let count = 1;
    let res ;
    function dfs (node){
        if(res)return 
        if(!node) return 
        dfs(node.right);
        if(k===count++){
            res= node.val;
            return 
        }
        dfs(node.left)
    }
    dfs(root)
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# N叉树的前序遍历(简单) (opens new window)

var preorder = function(root,arr=[]) {
    if(!root)return arr
    arr.push(root.val)
    root.children.forEach((val)=>{
        preorder(val,arr)
    })
    return arr
};
1
2
3
4
5
6
7
8

# N叉树的后序遍历(简单) (opens new window)

DFS递归

const postorder = function (root)
{
    if(root ===null){
        return root
    }
    const res =[]
    function dfs(root){
        if(root ===null){
            return 
        }
        for(let i =0;i<root.children.length;i++){
            dfs (root.children[i])
        }   
        res.push(root.val)
    }
    dfs(root)
    return res
}
//时间复杂度: O(n)
//空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 二叉树的层序遍历(中等) (opens new window)

  • DFS 深度优先遍历

const levelOrder = function(root,depth=0,res=[]) {
    if(!root)return res
    if(!res[depth]) {
        res[depth]=[]
    }
    res[depth].push(root.val)
    levelOrder(root.left,depth+1,res)
    levelOrder(root.right,depth+1,res)
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
  • BFS 广度优先遍历

根据层次 返回其对应的结果集合

  1. 边界处理，初始化队列 queue 和存放结果的数组 res。
  2. 外层循环遍历层级结构，内层循环遍历每一层的子节点。
  3. 遍历时需要记录当前层的遍历次数 len 以及当前层的节点数组 arr。
  4. 取得 node 依次出队，并依次存入当前层的节点数组中。
  5. 若存在左右子节点，则依次入队，并更新 len。
  6. 遍历完后返回结果 res。
const levelOrder =function(root){
    if(!root) return []
    const queue =[root]
    const res =[]
    while (queue.length>0){
        const arr =[]
        let len =queue.length
        while(len){
            let node =queue.shift()
            arr.push(node.val)
            if(node.left){
                queue.push(node.left)
            }
            if(node.right){
                queue.push(node.right)
            }
            len --
        }
        res.push(arr)
    }
    return res
}
//时间复杂度: O(n)
//空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 剑指Offer32. 从上到下打印二叉树II(简单) (opens new window)

  • 解题思路

这道题其实就是我们二叉树的层序遍历，将每一层的节点依次输出。这里可以使用一个技巧，增加一个变量k代表当前遍历到二叉树的第几层，默认为0，即默认是二叉树的第一层

  • 首先，先设计一下我们的递归函数

    • 函数意义：将 root 为根节点端的左子树和右子树添加到当前层k所在的数组中

    • 边界条件：root 为空时无需遍历，直接返回，直接返回结果数组

    • 递归过程：分别递归遍历 root 的左子树和右子树，别忘了层数需要加1

function levelOrder(root: TreeNode | null,k=0, res: number[][] = []): number[][] {
    // 边界条件，当root不存在时，直接返回结果数组
    if(!root) return res;
    // 如果结果数组的长度为k,说明我们准备遍历新的一层，但这层还没有数组来存放数据，所以要新建一个数组放到结果数组末尾
    if(res.length===k) res.push([]);
    // 将根节点的值放到第k位的数组中
    res[k].push(root.val);
    // 递归遍历左子树、右子树
    levelOrder(root.left, k+1, res);
    levelOrder(root.right, k+1, res);
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# 二叉树的层序遍历Ⅱ (opens new window)

function _lavelOrder(root: TreeNode|null, k: number, arr: number[][] = []): number[][] {
    if(!root) return arr;
    if(arr.length===k) arr.push([]);
    arr[k].push(root.val);
    _lavelOrder(root.left, k+1, arr);
    _lavelOrder(root.right, k+1, arr);
    return arr;

}

function levelOrderBottom(root: TreeNode | null): number[][] {
    const res = _lavelOrder(root, 0);
    // 使用双指针方式交换反转数组
    for(let i=0,j=res.length-1;i<j;i++,j--) {
        [res[i], res[j]] = [res[j], res[i]];
    }
    return res;
    // 也可以直接使用数组自带的反转方法
    // return res.reverse();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 二叉树的锯齿形层序遍历 (opens new window)

  • 解题思路

这一题其实是上面两题思路的综合，我们只需要先按照正常的层序遍历输出得到结果数组，然后将结果数组中的奇数行进行翻转就可以了。

当然，我们可以用更好的方法，就是在进行层序遍历时，直接判断当前的层数k是奇数还是偶数，如果是奇数就往数组前面添加元素，否则往数组后面添加元素，这样就不需要额外再反转数组了。

function _zigzagLevelOrder(root: TreeNode | null, k:number=0, res: number[][]=[]): number[][] {
    if(!root) return res;
    if(k===res.length) res.push([]);
    res[k].push(root.val);
    _zigzagLevelOrder(root.left, k + 1, res);
    _zigzagLevelOrder(root.right, k + 1, res);
    return res;
};

function zigzagLevelOrder(root: TreeNode | null): number[][] {
    const res = _zigzagLevelOrder(root);
    // 将奇数行反转
    return res.map((item, index) => {
        if(index&1) {
            item = item.reverse();
        }
        return item;
    })
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 二叉树的光照节点(剑指 Offer II 046. 二叉树的右侧视图) (opens new window)

  • 题目
// 从右侧有一束光照过来，请输出光能照到的所有节点。

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

//         3
//        / \
//       9   20
//           / \
//          15  7
//          /
//         16

// 输出：
// [3,20,7,16]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • dfs

思路：使用DFS递归遍历树的所有节点，创建结果数组res，将当前节点的层级当做res的下标、val当做res的值，以此更新res，右边节点的值会不断覆盖左边节点，得到的数组就是从右侧所能看到的节点值。

var rightSideView = function (root) {
    const res = [];
    function dfs(node, level) {
        if (!node) return;
        res[level] = node.val;
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
  • 双队列 层序遍历

每层从右节点开始加入 那么每层的第一个·元素就是我们所看到的节点

function exposedElement(root){
    if(!root){
        return []
    }
    const queue =[root]
    const res = []
    while(queue.length){
        let lastVal = null
        for(let i =queue.length;i>0;i--){
            const node = queue.shift()
            lastVal =node.val;
            if(node.left){
                queue.unshift(node.left);
            }
            if(node.right){
                queue.unshift(node.right)
            }   
        }
        if(lastVal){
            res.push(lastVal)
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 树的子结构(中等) (opens new window)

  1. 首先找到A树中和B树根节点相同的节点

  2. 从此节点开始,递归AB树比较是否有不同节点


function HasSubtree(pRoot1,pRoot2){
    let result =false 
    if(pRoot1 && pRoot2){
        if(pRoot1.val ===pRoot2.val){
            result = compare(pRoot1,pRoot2)
        }
        if(!result){
            result = HasSubtree(pRoot1.right,pRoot2);
        }
        if(!result){
            result = HasSubtree(pRoot1.left,pRoot2);
        }
    }
    return result
}

function compare(pRoot1,pRoot2){
   if(pRoot2 ===null){
       return true
   }
   if(pRoot1===null){
       return false
   }
   if(pRoot1.val !== pRoot2.val){
       return false
   }
   return compare(pRoot1.right,pRoot2.right) && compare(pRoot1.left, pRoot2.left);    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 寻找重复的子树(中等) (opens new window)

  • 后序遍历+序列化+hash存储

  1. 用递归，就必须知道以当前节点以它为根的这棵二叉树长什么样，还需要知道以其它节点为根的二叉树长什么样，才能进行比较

  2. 要解决以当前节点为根的二叉树长什么样，就得用序列化它的结构

  3. 要知道以当前节点为根的二叉树长什么样，用后序遍历最是佳的方式

  4. 要知道以其它节点为根的二叉树长什么样，就得要把序列化二叉树的结构的结果存储起来


const findDuplicateSubtree =function (root){
    // 记录所有子树
    const count = new Map();
    const res =[]
    const collect= (node)=>{
        // 对于空节点,可以用一个特殊字符表示
        if(!node){
            return "#"
        }
        //将左右子树序列化成字符串，左右子树加上自己，就是以为自己为根的二叉树序列化结果
        const key = node.val + "," +collect(node.left)+collect(node.right)
        //让每个节点把自己的序列化结果存进去，对于每个节点，就可以知道有没有其他节点的子树和自己重复了
        let freq = count.get(key) || 0;
        if(freq ==1){
            //有人和我重复，把自己加入结果列表
            res.push(node)
        }
        count.set(key,freq+1);
        return key;
    }
    collect(root)
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 验证二叉搜索树(中等) (opens new window)

  • 中序遍历

二叉搜索树需要满足以下三条件：

  • 节点的左子树只包含小于当前节点的数
  • 节点的右子树只包含大于当前节点的数
  • 所有左子树和右子树自身必须也是二叉搜索树
  1. 二叉搜索树在中序遍历得到序列一定是升序
  2. 进行中序遍历，判断当前节点是否大于前一个节点
  3. 如果比前一个大，说明满足，则继续遍历，否则直接返回 false
const isValidBST =function (root){
    let prev = -Infinity
    let result = true 
    function inorder(root){
        if(root === null){
            return 
        }
        inorder(root.left)
        if(root.val<=prev){
            result =false
            return 
        }
        prev =root.val
        inorder(root.right)
    }
    inorder(root)
    return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 二叉树的最近公共祖先(中等) (opens new window)

  • DFS递归
  1. 从根节点开始遍历，递归左右子树
  2. 递归终止条件：当前节点为空或者等于 p 或 q，返回当前节点
  3. p，q 可能在相同的子树中，也可能在不同的子树中
  4. 如果左右子树查到节点都不为空，则表示 p 和 q 分别在左右子树中，当前节点就是最近公共祖先
  5. 如果左右子树中有一个不为空，则返回为空节点
const lowestCommonAncestor =function (root,p,q){
    if(root ===null || root === p || root ===q ) return root
    
    let left = lowestCommonAncestor(root.left,p,q)
    let right = lowestCommonAncestor(root.right,p,q)

    if(left !==null && right !== null){
        return root
    }

    return left !== null ?left:right
}


//时间复杂度: O(n)
//空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 重建二叉树(中等) (opens new window)

  1. 前序遍历的第一个元素一定是根节点，这里是3
  2. 找到根节点之后，根节点在中序遍历中把数组一分为二，即两个数组[9]和[15, 20, 7]，这两个数组分别是根节点3的左子树和右子树的中序遍历。
  3. 前序遍历数组去掉根节点之后是[9,20,15,7]，而这个数组的第1项[9]（左子树的大小）和后3项[20, 15, 7]（右子树的大小）又分别是左子树和右子树的前序遍历 到这里已经很明显了，用递归

function TreeNode(val){
    this.val =val;
    this.left =this.right =null;
}

const buildTee =function (preorder,inorder){
    if(preorder.length){
        let head =new TreeNode(preorder.shift())
        let index =inorrder.indexOf(head.val);
        head.left =buildTree(
            preorder.slice(0,index)
            inorder.slice(0,index)
        );
        head.right =buildTree(preorder.slice(index),inorder.slice(index+1));
        return head;
    }else{
        return null
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 二叉树的序列化和反序列化(困难) (opens new window)

  • DFS 递归

const serialize = function (root){
    const res =[]
    function dfs(node){
        if(node ===null){
            res.push(null)
            return 
        }
        res.push(node.val)
        dfs(node.left)
        dfs(node.right)
    }
    dfs(root)
    return res
}

const deserialize =function (data){
    function dfs(){
        if(data.length === 0) return null
        let val =data.shift()
        if(val ===null) return null
        let node = new TreeNode(val)
        node.left =dfs()
        node.right =dfs()
        return node
    }
    return dfs()
}

//时间复杂度: O(n)
//空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 参考链接

非线性表（树、堆) (opens new window)

小白都可以看懂对树与二叉树 (opens new window)

“树”业有专攻 (opens new window)

力扣++树 (opens new window)

拉钩教育-轻松搞定二叉树 (opens new window)

← 字符串 →