LeetCode精选Top面试题之二叉树的最大深度-一一网

这是我参与更文挑战的第5天，活动详情查看：更文挑战

前言

公众号给npy的前端秘籍

加vx?16639199716,拉你进群嗷~❤️

数据结构中的树还是很重要的，所以本次学习一下树和二叉树，做一下总结，分享给大家?

树的基本概念

树是一种分层数据的抽象模型
前端工作中常见的树包括：DOM树,级联选择,树形控件
JS没有树,但是可以用object和Array来构建树

{
    value:'zhejiang',
    lable:'zhejiang',
    children:[
        {
          value:'hangzhou',
          lable:'hangzhou',
          children:[
            {
                vlaue:'xihu',
                lable:'West Lake'
             }
           ]          
        }
    ]
}
复制代码

凡是满足分层结构的,都可以说是一棵树
树的常用操作：深度/广度优先遍历、先中后序遍历

树的基本术语

节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点度称为树的度；
叶节点或终端节点：度为零的节点；
非终端节点或分支节点：度不为零的节点；
父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
堂兄弟节点：父节点在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙；
森林：由m（m>=0）棵互不相交的树的集合称为森林。

二叉树的概念

二叉树是一种典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

树的深度和广度优先遍历

深度优先遍历:尽可能深的搜索树的分支
类似于我们看书，先看第一章第一小节，看完第一章以后再看第二章

深度优先遍历的口诀

访问根节点
对根节点的children挨个进行深度优先遍历

//dfs.js
const tree ={
    val:'a',
    children:[
        {
            val:'b',
            children:[
                {
                    val:'d'
                },
                {
                     val:'e'
                }
            ]
        },
        {
            val:'c'
            children:[
            {
            	val:'f'
             },
            {
                val:'g'
            }
            ]
        }
    ]
};
const dfs =(root)=>{
    console.log(root.val);
    root.children.forEach((child)=>{
        dfs(child)
    })
}
dfs(tree)
复制代码

广度优先遍历:先访问离根节点最近的节点
类似于我们看书，先看这本书的标题，再看目录，然后再深入看

广度优先遍历的算法口诀

新建一个节点,把根节点入队
把队头出队并访问
把队头的children挨个入队
重复第二、三步、直到队列为空

//bfs.js
const tree ={
    val:'a',
    children:[
        {
            val:'b',
            children:[
                {
                    val:'d'
                },
                {
                     val:'e'
                }
            ]
        },
        {
            val:'c'
            children:[
            {
            	val:'f'
             },
            {
                val:'g'
            }
            ]
        }
    ]
};
const bfs =(root)=>{
    const q =[root];
    while(q.length>0){
        const n =q.shift();
        console.log(n)
        n.children.forEach(child=>{
            q.push(child)
        })
    }
}
bfs(tree)
复制代码

二叉树的遍历

我们知道对于二叉树的遍历而言，有常见得三种遍历方式，分别是以下三种：

前序遍历
中序遍历
后序遍历

对于任何一种遍历方式而言，我们不仅需要掌握它的非递归版本，同时对于它的递归版本来说，更是考察一个人的算法基本功，那么接下来，我们来看看吧。

前序遍历

点击这里，练习二叉树的前序遍历

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

解题思路：

先访问根节点
对根节点的左子树进行先序遍历
对根节点的右子树进行先序遍历
根->左->右

那么根据我们对前序遍历的理解，我们可以写出解题代码?

/**
 * 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 preorderTraversal = function(root) {
    let res = []
    this.preOrder = function(root) {
        if(!root){return}
        res.push(root.val)
        preOrder(root.left);
        preOrder(root.right)
    }
    preOrder(root)
    return res
};
//时间复杂度O（n）
//空间复杂度O（n）
复制代码

非递归版本?

对于非递归的话，我们需要借助一个数据结构去存储它的节点，需要使用的就是栈，它的思路可以借鉴?

根节点为目标节点，开始向它子节点遍历

1.访问目标节点

2.左孩子入栈 -> 直至左孩子为空的节点

3.节点出栈，以右孩子为目标节点，再依次执行1、2、3


  let preorderTraversal = (root, arr = []) => {
    const stack = [], res = []
    let current = root
    while(current || stack.length > 0) {
      while (current) {
        res.push(current.val)
        stack.push(current)
        current = current.left
      }
      current = stack.pop()
      current = current.right
    }
    return res
  }
复制代码

中序遍历

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

解题思路：

对根节点的左子树进行中序遍历
访问根节点
对根节点的右子树进行中序遍历
左->根->右

递归版本?

var inorderTraversal = function (root) {
    const res = []
    const rec = (n) => {
        if (!n) { return; }
        rec(n.left)
        res.push(n.val)
        rec(n.right)
    }
    rec(root)
    return res;
};
//时间复杂度O(n)
//空间复杂度O(n)
复制代码

非递归版本，这里就不解释了，跟前序遍历一样，思路一样，用栈维护节点信息。

const inorderTraversal = (root, arr = []) => {
  const stack = [], res = []
  let current = root
  while(current || stack.length > 0) {
    while (current) {
      stack.push(current)
      current = current.left
    }
    current = stack.pop()
    res.push(current.val)
    current = current.right
  }
  return res
}
复制代码

后续遍历

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

解题思路:

对根节点的左子树进行后序遍历
对根节点的右子树进行后序遍历
访问根节点
左->右->根

递归版本?

  if(root) {
    postorderTraversal(root.left, arr)
    postorderTraversal(root.right, arr)
    arr.push(root.val)
  }
  return arr
}
复制代码

非递归版本?
其实，嗯，做完前面两个后，会发现都是有套路滴~

const postorderTraversal = (root, arr = []) => {
  const stack = [], res = []
  let current = root, last = null  // last指针记录上一个节点
  while(current || stack.length > 0) {
    while (current) {
      stack.push(current)
      current = current.left
    }
    current = stack[stack.length - 1]
    if (!current.right || current.right == last) {
      current = stack.pop()
      res.push(current.val)
      last = current
      current = null              // 继续弹栈
    } else {
      current = current.right
    }
  }
  return res
}
复制代码

题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

  3
 / \
9  20
  /  \
 15   7
复制代码

返回它的最大深度 3 。

递归思路：

每次分别遍历左节点,以及右节点,然后对比两者,取最大值
这样子，每次递归的话，深度都加1

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

非递归思路:

求最大深度，考虑使用深度优先遍历
在深度优先遍历过程中,记录每个节点所在的层级,找出最大的层级即可
思路：
- 新建一个变量，记录最大深度
- 深度优先遍历整棵树,并记录每个节点的层级,同时不断刷新最大深度这个变量
- 遍历结束返回最大深度这个变量

 */
var maxDepth = function (root) {
    let res = 0;
    const dfs = (n, l) => {
        if (!n) { return; }
        if (!n.left && !n.right) {
            res = Math.max(res, l)
        }
        dfs(n.left, l + 1)
        dfs(n.right, l + 1)
    }
    dfs(root, 1)
    return res;
};
//代码循环了n次  O(n)
//空间复杂度 O(logn)  嵌套的次数递归形成了一个堆栈
复制代码

今日加餐

今日加餐我选择了LeetCode111、二叉树的最小深度，两个一起恰，味道更好嗷~

递归思路:

判断当前节点是否是根，并且为空,是的话,返回0

当前节点的左右节点都是null,也就是叶子节点时,此时就是目标节点,最小深度,返回1

当前节点的左节点不为null,找左子树的深度

当前节点的右节点不为null,找右子树的深度

比较两者,返回的就是3和4条件的最小值,并且加1

一遍看代码一遍思路?

var minDepth = function (root) {
    if (root == null) return 0
    if (root.left == null && root.right == null) return 1
    let max = 10000;
    if (root.left) max = Math.min(max, minDepth(root.left))
    if (root.right) max = Math.min(max, minDepth(root.right))
    return max + 1
};
复制代码

非递归思路:

求最小深度、考虑使用广度优先遍历
在广度优先遍历过程中,遇到叶子节点,停止遍历，返回节点层级
思路：
- 广度优先遍历整棵树，并记录每个节点的层级
- 遇到叶子节点，返回节点层级,停止变量

做多的BFS，就会发现，原来都是套路题?

var minDepth = function (root) {
    if (!root) { return 0; }
    const q = [[root, 1]];
    while (q.length) {
        const [n,l] = q.shift();
        if (!n.left && !n.right) {
            return l;
        }
        if (n.left) {
            q.push([n.left, l + 1])
        } if (n.right) {
            q.push([n.right, l + 1])
        }
    }
};
//时间复杂度O(n)
//空间复杂度O(n)  n是树中节点的数量
复制代码