(1条消息) 万字长文!二叉树入门和刷题看这篇就够了!

今天是小浩算法 “365刷题计划” 二叉树入门 - 整合篇。本篇作为入门整合篇,已经砍去难度较大的知识点,所有列出的内容,均为必须掌握。因为很长,写下目录:

  • 二叉树是啥

  • 二叉树的最大深度(DFS)

  • 二叉树的层次遍历(BFS)

  • 二叉搜索树验证

  • 二叉搜索树查找

  • 二叉搜索树删除

  • 平衡二叉树

  • 完全二叉树

  • 二叉树的剪枝

01

PART

二叉树是啥

二叉树有多重要?单就面试而言,在 leetcode 中二叉树相关的题目占据了300多道,近三分之一。同时,二叉树在整个算法板块中还起到承上启下的作用:不但是数组和链表的延伸,又可以作为图的基础。总之,非常重要!

什么是二叉树?官方是这样定义的:在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

上面那是个玩笑,二叉树长这样:

二叉树常被用于实现二叉查找树二叉堆。树比链表稍微复杂,因为链表是线性数据结构,而树不是。树的问题很多都可以由广度优先搜索或深度优先搜索解决。

一般而言,我们会看到下面这些与树相关的术语:

小浩概念

与树相关的术语

树的结点(node):包含一个数据元素及若干指向子树的分支;

孩子结点(child node):结点的子树的根称为该结点的孩子;

双亲结点:B 结点是A 结点的孩子,则A结点是B 结点的双亲;

兄弟结点:同一双亲的孩子结点;堂兄结点:同一层上结点;

祖先结点: 从根到该结点的所经分支上的所有结点

子孙结点:以某结点为根的子树中任一结点都称为该结点的子孙

结点层:根结点的层定义为1;根的孩子为第二层结点,依此类推;

树的深度:树中最大的结点层

结点的度:结点子树的个数

树的度:树中最大的结点度。

叶子结点:也叫终端结点,是度为 0 的结点;

分枝结点:度不为0的结点;

有序树:子树有序的树,比如家族树;

无序树:不考虑子树的顺序;

了解了上面的基本概念之后。我们将通过几道例题,为大家引入树的经典操作。

02

PART

二叉树最大深度

复习上面的概念:树的深度指的是树中最大的结点层。

第104题:给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

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

示例:

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

3/ \9  20/  \15   7

基本概念掌握:每个节点的深度与它左右子树的深度有关,且等于其左右子树最大深度值加上 1。即:

maxDepth(root) = max(maxDepth(root.left),maxDepth(root.right)) + 1

以 [3,9,20,null,null,15,7] 为例:

  • 我们要对根节点的最大深度求解,就要对其左右子树的深度进行求解

  • 我们看出。以4为根节点的子树没有左右节点,其深度为1。而以20为根节点的子树的深度,同样取决于它的左右子树深度。

  • 对于15和7的子树,我们可以一眼看出其深度为1。

  • 由此我们可以得到根节点的最大深度为

maxDepth(root-3)
=max(maxDepth(sub-4),maxDepth(sub-20))+1
=max(1,max(maxDepth(sub-15),maxDepth(sub-7))+1)+1
=max(1,max(1,1)+1)+1
=max(1,2)+1
=3

根据分析,我们通过递归进行求解:

1//Go2func maxDepth(root *TreeNode) int {3    if root == nil {4        return 05    }6    return max(maxDepth(root.Left), maxDepth(root.Right)) + 17}89func max(a int, b int) int {10    if a > b {11        return a12    }13    return b14}

其实我们上面用的递归方式,本质上是使用了DFS的思想。所以这里就可以引出什么是DFS:深度优先搜索算法(Depth First Search),对于二叉树而言它沿着树的深度遍历树的节点,尽可能深的搜索树的分支,这一过程一直进行到已发现从源节点可达的所有节点为止。( 注意,这里的前提是对二叉树而言。DFS本身作为图算法的一种,在后续我会单独拉出来和回溯放一起讲。)

如上图二叉树,它的访问顺序为:

A-B-D-E-C-F-G

到这里,我们思考一个问题?虽然我们用递归的方式根据DFS的思想顺利完成了题目。但是这种方式的缺点却显而易见。因为在递归中,如果层级过深,我们很可能保存过多的临时变量,导致栈溢出。这也是为什么我们一般不在后台代码中使用递归的原因。如果不理解,下面我们详细说明:

事实上,函数调用的参数是通过栈空间来传递的,在调用过程中会占用线程的栈资源。而递归调用,只有走到最后的结束点后函数才能依次退出,而未到达最后的结束点之前,占用的栈空间一直没有释放,如果递归调用次数过多,就可能导致占用的栈资源超过线程的最大值,从而导致栈溢出,导致程序的异常退出。

所以,我们引出下面的话题:如何将递归的代码转化成非递归的形式。这里请记住,基本所有的递归转非递归,都可以通过栈来进行实现。非递归的DFS,代码如下:

1//java2private List<TreeNode> traversal(TreeNode root) {3    List<TreeNode> res = new ArrayList<>();4    Stack<TreeNode> stack = new Stack<>();5    stack.add(root);6    while (!stack.empty()) {7        TreeNode node = stack.peek();8        res.add(node);9        stack.pop();10        if (node.right != null) {11            stack.push(node.right);12        }13        if (node.left != null) {14            stack.push(node.left);15        }16    }17    return res;18}

上面的代码,唯一需要强调的是,为什么需要先右后左压入数据?是因为我们需要将先访问的数据,后压入栈(请思考栈的特点)。

如果不理解代码,请看下图:

说明:

  • 1:首先将a压入栈

  • 2:a弹栈,将c、b压入栈(注意顺序)

  • 3:b弹栈,将e、d压入栈

  • 4,5:d、e、c弹栈,将g、f压入栈

  • 6:f、g弹栈

至此,非递归的 DFS 就讲解完毕了。那如何通过非递归DFS的方式,来对本题求解呢?相信已经很简单了,这个下去自己试试就ok了了。

03

PART

二叉树的层次遍历

在上文中,我们通过例题学习了二叉树的DFS(深度优先搜索),其实就是沿着一个方向一直向下遍历。那我们可不可以按照高度一层一层的访问树中的数据呢?当然可以,就是本节中我们要讲的BFS(宽度优先搜索),同时也被称为广度优先搜索。

第102题:给定一个二叉树,返回其按层次遍历的节点值。(即逐层地,从左到右访问所有节点)。

例如:

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

3

/ \

9  20

/  \

15   7

返回其层次遍历结果:[[3],[9,20],[15,7]]

BFS,广度/宽度优先。说白了就是从上到下,先把每一层遍历完之后再遍历一下一层。假如我们的树如下:

按照BFS,访问顺序如下:

a->b->c->d->e->f->g

了解了BFS,我们开始对本题进行分析。同样,我们先考虑本题的递归解法。想到递归,我们一般先想到DFS。我们可以对该二叉树进行先序遍历(根左右的顺序),同时,记录节点所在的层次level,并且对每一层都定义一个数组,然后将访问到的节点值放入对应层的数组中。

假设给定二叉树为[3,9,20,null,null,15,7],图解如下:

根据分析,代码如下:

1//Go2func levelOrder(root *TreeNode) [][]int {3    return dfs(root, 0, [][]int{})4}56func dfs(root *TreeNode, level int, res [][]int) [][]int {7    if root == nil {8        return res9    }10    if len(res) == level {11        res = append(res, []int{root.Val})12    } else {13        res[level] = append(res[level], root.Val)14    }15    res = dfs(root.Left, level+1, res)16    res = dfs(root.Right, level+1, res)17    return res18}

上面的解法,其实相当于是用DFS的方法实现了二叉树的BFS。那我们能不能直接使用BFS的方式进行解题呢?当然可以。我们使用Queue的数据结构。我们将root节点初始化进队列,通过消耗尾部,插入头部的方式来完成BFS。

具体步骤如下图:

根据分析,完成代码:

1//Go2func levelOrder(root *TreeNode) [][]int {3    var result [][]int4    if root == nil {5        return result6    }7    // 定义一个双向队列8    queue := list.New()9    // 头部插入根节点10    queue.PushFront(root)11    // 进行广度搜索12    for queue.Len() > 0 {13        var currentLevel []int14        listLength := queue.Len()15        for i := 0; i < listLength; i++ {16            // queue.Back():返回队列中最后一个元素17            // queue.Remove(queue.Back()).(*TreeNode) : 移除队列中最后一个元素并将其转化为TreeNode类型18            node := queue.Remove(queue.Back()).(*TreeNode)19            currentLevel = append(currentLevel, node.Val)20            if node.Left != nil {21                queue.PushFront(node.Left)22            }23            if node.Right != nil {24                queue.PushFront(node.Right)25            }26        }27        result = append(result, currentLevel)28    }29    return result30}

04

PART

二叉搜索树

BST是二叉搜索树,很重要。BST是二叉搜索树,很重要。BST是二叉搜索树,很重要。重要的事情说三遍。

第98题:给定一个二叉树,判断其是否是一个有效的二叉搜索树。

示例 1:

输入:

5

/ \

1   4

/ \

3   6

输出: false

解释: 输入为: [5,1,4,null,null,3,6]。

根节点的值为 5 ,但是其右子节点值为 4 。

要验证二叉搜索树,首先得知道啥是二叉搜索树。二叉搜索树(Binary Search Tree),(又:二叉查找树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉搜索树

这里强调一下子树的概念:设T是有根树,a是T中的一个顶点,由a以及a的所有后裔(后代)导出的子图称为有向树T的子树。具体来说,子树就是树的其中一个节点以及其下面的所有的节点所构成的树。比如下面这就是一颗二叉搜索树:

下面这两个都不是:

  • 图中4节点位置的数值应该大于根节点

  • 图中3节点位置的数值应该大于根节点

回到题目,那我们如何来验证一颗二叉搜索树?首先看完题目,我们很容易想到 遍历整棵树,比较所有节点,通过 左节点值<节点值,右节点值>节点值 的方式来进行求解。但是这种解法是错误的,因为对于任意一个节点,我们不光需要左节点值小于该节点,并且左子树上的所有节点值都需要小于该节点。(右节点一致)所以我们在此引入上界与下界,用以保存之前的节点中出现的最大值与最小值

代码其实很简单:

1//GO2func isValidBST(root *TreeNode) bool {3    if root == nil{4        return true5    }6    return isBST(root,math.MinInt64,math.MaxInt64)7}89func isBST(root *TreeNode,min, max int) bool{10    if root == nil{11        return true12    }13    if min >= root.Val || max <= root.Val{14        return false15    }16    return isBST(root.Left,min,root.Val) && isBST(root.Right,root.Val,max)17}

难就难在,可能大家看不懂这个递归!没事,祭出大杀器:

这里需要强调的是,在每次递归中,我们除了进行左右节点的校验,还需要与上下界进行判断。其余的就很简单了。

05

PART

BST的查找

在上文中,我们学习了二叉搜索树。那我们如何在二叉搜索树中查找一个元素呢?

第700题:给定二叉搜索树(BST)的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在,则返回 NULL。

例如,给定二叉搜索树:

4

/ \

2   7

/ \

1   3

搜索: 2

你应该返回如下子树:

2

/ \

1   3

在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。

先复习一下,二叉搜索树(BST)的特性:

1.若它的左子树不为空,则所有左子树上的值均小于其根节点的值

2.若它的右子树不为空,则所有右子树上的值均大于其根节点得值

3.它的左右子树也分别为二叉搜索树

如下图就是一棵典型的BST:

现在我们来看题,假设目标值为 val。根据BST的特性,我们可以很容易想到查找过程(上面的验证比查找稍难一点):

  • 如果val小于当前结点的值,转向其左子树继续搜索;

  • 如果val大于当前结点的值,转向其右子树继续搜索;

  • 如果已找到,则返回当前结点。

很简单,不是吗?然后我们可以给出迭代和递归两种解法(给个Java的吧!):

1//java23//递归4public TreeNode searchBST(TreeNode root, int val) {5    if (root == null)6        return null;7    if (root.val > val) {8        return searchBST(root.left, val);9    } else if (root.val < val) {10        return searchBST(root.right, val);11    } else {12        return root;13    }14}1516//迭代17public TreeNode searchBST(TreeNode root, int val) {18    while (root != null) {19        if (root.val == val) {20            return root;21        } else if (root.val > val) {22            root = root.left;23        } else {24            root = root.right;25        }26    }27    return null;28}

06

PART

BST的删除

查找有了,下面自然就要讲删除。(为啥说我要着重墨在BST上面,因为BST这两年在面试时非常高频。面试官不可能说问你一个普通二叉树的题目,要么就是问堆,要么就是问BST,或者就直接DFS考察回溯。)

第450题:给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

首先找到需要删除的节点;

如果找到了,删除它。

说明:要求算法时间复杂度为 O(h),h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]

key = 3

5

/ \

3   6

/ \   \

2   4   7

给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

5

/ \

4   6

/     \

2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

5

/ \

2   6

\   \

4   7

如果你看到了这里,相信肯定知道BST是个啥了。所以直接分析题目。我们要删除BST的一个节点,首先需要找到该节点。而找到之后,会出现三种情况。

  1. 待删除的节点左子树为空,让待删除节点的右子树替代自己。

  2. 待删除的节点右子树为空,让待删除节点的左子树替代自己。

  3. 如果待删除的节点的左右子树都不为空。我们需要找到比当前节点小的最大节点(前驱),来替换自己

    或者比当前节点大的最小节点(后继),来替换自己。

分析完毕,直接上代码。这里我们给出通过后继节点来替代自己的方案(可以自行实现另一种方案):

1//go2func deleteNode(root *TreeNode, key int) *TreeNode {3    if root == nil {4        return nil5    }6    if key < root.Val {7        root.Left = deleteNode( root.Left, key )8        return root9    }10    if key > root.Val {11        root.Right = deleteNode( root.Right, key )12        return root13    }14    //到这里意味已经查找到目标15    if root.Right == nil {16        //右子树为空17        return root.Left18    }19    if root.Left == nil {20        //左子树为空21        return root.Right22    }23    minNode := root.Right24    for minNode.Left != nil {25        //查找后继26        minNode = minNode.Left27    }28    root.Val = minNode.Val29    root.Right = deleteMinNode( root.Right )30    return root31}323334func deleteMinNode( root *TreeNode ) *TreeNode {35    if root.Left == nil {36        pRight := root.Right37        root.Right = nil38        return pRight39    }40    root.Left = deleteMinNode( root.Left )41    return root42}

07

PART

平衡二叉树

BST讲解完了。上面也说了,别人考察我们肯定是考察特殊的。那二叉树里还有啥特殊的东东嘞?平衡二叉树算是一个。

第110题:给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

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

示例 1:

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

3

/ \

9  20

/  \

15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

1

/ \

2   2

/ \

3   3

/ \

4   4

返回 false 。

题其实是一道很简单的题,主要是拿来复习一下高度。我们想判断一棵树是否满足平衡二叉树,无非就是判断当前结点的两个孩子是否满足平衡,同时两个孩子的高度差是否超过1。那只要我们可以得到高度,再基于高度进行判断即可

这里唯一要注意的是,当我们判定其中任意一个节点如果不满足平衡二叉树时,那说明整棵树已经不是一颗平衡二叉树,我们可以对其进行阻断,不需要继续递归下去

然后还有一个初学者容易懵逼的:

这玩意,并不是平衡二叉树。上代码:

1//GO2func isBalanced(root *TreeNode) bool {3    if root == nil {4        return true5    }6    l := maxDepth(root.Left)7    r := maxDepth(root.Right)8    if abs(l-r)>1 {9        return false10    }11    if isBalanced(root.Left){12        return true13    }14    return isBalanced(root.Right)15}1617func maxDepth(root *TreeNode) int {18    if root == nil {19        return 020    }21    return max(maxDepth(root.Left),maxDepth(root.Right)) + 122}2324func max(a,b int) int {25    if a > b {26        return a27    }28    return b29}3031func abs(a int) int {32    if a < 0 {33        return -a34    }35    return a 36}

08

PART

完全二叉树

还有啥特殊的,要捞出来讲一讲的?

第222题:给出一个完全二叉树,求出该树的节点个数。

说明:

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

示例:

输入:

1

/ \

2   3

/ \  /

4  5 6

输出: 6

老样子,我们得说说啥是完全二叉树。完全二叉树由满二叉树引出,先来了解一下什么是满二叉树。如果二叉树中除了叶子结点,每个结点的度都为 2,则此二叉树称为满二叉树。(二叉树的度代表某个结点的孩子或者说直接后继的个数,这个在上面已经说过了。对于二叉树而言,1度是只有一个孩子或者说单子树,2度是有两个孩子或者说左右子树都有。)

那什么又是完全二叉树呢:如果二叉树中除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布,则此二叉树被称为完全二叉树。比如下面这颗:

这个就不是:

上面做了这么多题了,你应该能想到我要说啥 --- 递归。二叉树的题目基本上都可以递归求解。

1func countNodes(root *TreeNode) int {2    if root != nil {3        return 045    }6    return 1 + countNodes(root.Right) + countNodes(root.Left)7}

但是很明显,出题者肯定不是要这种答案。因为这种答案和完全二叉树一毛钱关系都没有。所以我们继续思考。

由于题中已经告诉我们这是一颗完全二叉树,我们又已知了完全二叉树除了最后一层,其他层都是满的,并且最后一层的节点全部靠向了左边。那我们可以想到,可以将该完全二叉树可以分割成若干满二叉树和完全二叉树满二叉树直接根据层高h计算出节点为2^h-1,然后继续计算子树中完全二叉树节点。那如何分割成若干满二叉树和完全二叉树呢?对任意一个子树,遍历其左子树层高left,右子树层高right,相等左子树则是满二叉树,否则右子树是满二叉树。这里可能不容易理解,我们看图。

假如我们有树如下:

我们看到根节点的左右子树高度都为3,那么说明左子树是一颗满二叉树。因为节点已经填充到右子树了,左子树必定已经填满了。所以左子树的节点总数我们可以直接得到,是2^left - 1,加上当前这个root节点,则正好是2^3,即 8。然后只需要再对右子树进行递归统计即可。

那假如我们的树是这样:

我们看到左子树高度为3,右子树高度为2。说明此时最后一层不满,但倒数第二层已经满了,可以直接得到右子树的节点个数。同理,右子树节点+root节点,总数为2^right,即2^2。再对左子树进行递归查找。

根据分析,得出代码:

1//java2class Solution {3    public int countNodes(TreeNode root) {4        if (root == null) {5            return 0;6        }7        int left = countLevel(root.left);8        int right = countLevel(root.right);9        if (left == right) {10            return countNodes(root.right) + (1 << left);11        } else {12            return countNodes(root.left) + (1 << right);13        }14    }1516    private int countLevel(TreeNode root) {17        int level = 0;18        while (root != null) {19            level++;20            root = root.left;21        }22        return level;23    }24}

09

PART

二叉树的剪枝

该讲的都讲了,突然想到忘了一个经典操作 - 剪枝。迅速补上!非常重要!这里额外说一点,就本人而言,对这个操作以及其衍化形式的使用会比较频繁。因为我是做反欺诈的,机器学习里有一个概念叫做决策树,那如果一颗决策树完全生长,就会带来比较大的过拟合问题。因为完全生长的决策树,每个节点只会包含一个样本。所以我们就需要对决策树进行剪枝操作,来提升整个决策模型的泛化能力... 听不懂也没关系,简单点讲,就是我觉得这个很重要,或者每道算法题都很重要。如果你在工作中没有用到,不是说明算法不重要,而可能是你还不够重要。

第814题:给定二叉树根结点 root ,此外树的每个结点的值要么是 0,要么是 1。返回移除了所有不包含 1 的子树的原二叉树。

( 节点 X 的子树为 X 本身,以及所有 X 的后代。)

示例1:

输入: [1,null,0,0,1]

输出: [1,null,0,null,1]

解释:

只有红色节点满足条件“所有不包含 1 的子树”。

右图为返回的答案。

示例2:

输入: [1,0,1,0,0,0,1]

输出: [1,null,1,null,1]

示例3:

输入: [1,1,0,1,1,0,1,0]

输出: [1,1,0,1,1,null,1]

说明:

给定的二叉树最多有 100 个节点。

每个节点的值只会为 0 或 1 。

还是先解释一下,啥是剪枝:假设有一棵树,最上层的是root节点,而父节点会依赖子节点。如果现在有一些节点已经标记为无效,我们要删除这些无效节点。如果无效节点的依赖的节点还有效,那么不应该删除,如果无效节点和它的子节点都无效,则可以删除。剪掉这些节点的过程,称为剪枝,目的是用来处理二叉树模型中的依赖问题

说了好多遍了,二叉树的问题,大多都可以通过递归进行求解。直接分析。假设我们有二叉树如下:[0,1,0,1,0,0,0,0,1,1,0,1,0]:

长这样:

剪枝之后是这样:

剪什么大家应该都能理解。那关键是怎么剪?过程也很简单,在递归的过程中,如果当前结点的左右节点皆为空,且当前结点为0,我们就将当前节点剪掉即可。

其实很简单,直接看代码:

1func pruneTree(root *TreeNode) *TreeNode {2    return deal(root)3}45func deal(node *TreeNode) *TreeNode {6    if node == nil {7        return nil8    }9    node.Left = deal(node.Left)10    node.Right = deal(node.Right)11    if node.Left == nil && node.Right == nil && node.Val == 0 {12        return nil13    }14    return node15}

10

PART

(0)

相关推荐