【算法总结】五道常见的算法-二叉树

朱雀 2023-01-03 12:44 218阅读 0赞

# 前言 #

前段时间，写了面试必备的一系列文章，反应还不错。有一些读者反馈说，能不能整理一些面试常见的算法。前段时间，我恰好总结了 LeetCode 常见的面试算法题目。

https://github.com/gdutxiaoxu/Android\_interview

刚开始准备刷算法题目的时候，感觉真的是好难，十道题目有九道是不会的。心中曾一万只草泥马跑过，自己怎么这么辣鸡。

慢慢得，我发现算法也是一个可以通过练习慢慢成长的。

1.  首先我们要掌握基本的数据结构，数组，链表，哈希表， Set，二叉树，堆，栈等。你要知道他们有什么优缺点，适应场景是什么，时间复杂度和空间复杂度是多少。而不能知道简单的 API。
2.  接着，掌握了这些基本的数据结构之后，一些基本的算法你也要掌握以下，比如快速排序，归并排序，对排序，二分查找。这些基本的一定要掌握，面试当中经常也会问到。
3.  分类刷题，我们在力扣上面可以看到，https://leetcode-cn.com/problemset/algorithms/ ，刷题是可以按标签来的。比如链表，数组，二分查找，二叉树，动态规划等
4.  学好算法不是一日之功，需要长期的积累。建议的做法是每天做一两道题，题目不在多，贵在于理解。坚持一两个月，你会发现你的感觉逐渐好起来了

**废话不多说了，开始进入今天的正文。**

# 二叉树的概念 #

俗话说得好，万丈高楼平地起。讲解算法之前，我们先来了解一下一些基本的概念。

二叉树（Binary Tree）是包含n个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

一棵典型的二叉树如下图所示：

![format_png][]

由上述的定义可以看出，二叉树中的节点至多包含两棵子树，分别称为左子树和右子树，而左子树和右子树又分别至多包含两棵子树。由上述的定义，二叉树的定义是一种递归的定义。

## 二叉树种类 ##

**满二叉树**

对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。

**完全二叉树**

对于一棵具有n个节点的二叉树按照层次编号，同时，左右子树按照先左后右编号，如果编号为i的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。

**二叉排序树：**

又称二叉查找树（Binary Search Tree），亦称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

*  若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 *  若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
 *  左、右子树也分别为二叉排序树；
 *  没有键值相等的节点

二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)（相当于顺序查找）

**平衡二叉树**：

又称 AVL 树。平衡二叉树是二叉搜索树的进化版，所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过 1。

**红黑树**：

红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。

**哈夫曼树**：

给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

## 遍历方式 ##

二叉树主要有四种遍历方式

*  先序(先根)遍历：即先访问根节点，再访问左孩子和右孩子
 *  中序遍历：先访问做孩子，再访问根节点和右孩子
 *  后序遍历：先访问左孩子，再访问右孩子，再访问根节点
 *  层次遍历：按照所在层数，从下往上遍历

前提：这里先给出测试中的二叉树结构，如下图所示

![format_png 1][]

该二叉树对应的几种遍历方式的结果顺序：

*  先序遍历：10->6->4->8->14->12->16
 *  中序遍历：4->6->8->10->12->14->16
 *  后序遍历：4->8->6->12->16->14->10
 *  层次遍历：10->6->14->4->8->12->16

# 递归 #

**递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。**  
特别地，在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况，这也正是递归的定义所在。格外重要的是，这个解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况

而在树当中，一棵树要么是空树，要么有两个指针，每个指针指向一棵树。树是一种递归结构，很多树的问题可以使用递归来处理。

## 1. 树的高度 ##

### 1.0 求二叉树的最大层数(最大深度) ###

104. Maximum Depth of Binary Tree (Easy)

Leetcode / 力扣

**这道题目的解法其实很简单**

*  如果二叉树为空，二叉树的深度为0
 *  如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1

1public int maxDepth(TreeNode root) {
    2    if (root == null) return 0;
    3    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    4}

### 1.1 二叉树的最小深度 ###

LeetCode：Minimum Depth of Binary Tree

给定一个二叉树，找出其最小深度。  
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

![format_png 2][]

**解题思路**

*  对于一个节点，如果左子树或者右子树为空，那么最小深度为 left + right + 1
 *  如果左子树和右子树都不为空，那么最小深度为 Math.min(left,right) + 1

1class Solution {
    2    public int minDepth(TreeNode root) {
    3        if(root == null)
    4            return 0;
    5        int left = minDepth(root.left);
    6        int right = minDepth(root.right);
    7        return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
    8    }
    9}

## 2. 平衡树 ##

110. Balanced Binary Tree (Easy)

1    3
    2   / \
    3  9  20
    4    /  \
    5   15   7

### 思路 ###

平衡树左右子树高度差都小于等于 1

1private boolean result = true;
     2
     3public boolean isBalanced(TreeNode root) {
     4    maxDepth(root);
     5    return result;
     6}
     7
     8public int maxDepth(TreeNode root) {
     9    if (root == null) return 0;
    10    int l = maxDepth(root.left);
    11    int r = maxDepth(root.right);
    12    if (Math.abs(l - r) > 1) result = false;
    13    return 1 + Math.max(l, r);
    14}

## 3. 两节点的最长路径 ##

543. Diameter of Binary Tree (Easy)

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

**解题思路：**

1.  因为最长直径不一定过根节点，所以需要分别以每一个节点为中心计算最长路径。
2.  用一个全局变量max来维护最长路径（左子树的深度+右子树的深度）。
3.  为了计算每个子树的深度，使用深度优先遍历计算树中每一个节点的深度（max（左子树深度，右子树深度））

1Input:
    2
    3         1
    4        / \
    5       2  3
    6      / \
    7     4   5
    8
    9Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

1private int max = 0;
     2
     3public int diameterOfBinaryTree(TreeNode root) {
     4    depth(root);
     5    return max;
     6}
     7
     8private int depth(TreeNode root) {
     9    if (root == null) return 0;
    10    int leftDepth = depth(root.left);
    11    int rightDepth = depth(root.right);
    12    max = Math.max(max, leftDepth + rightDepth);
    13    return Math.max(leftDepth, rightDepth) + 1;
    14}

## 4. 翻转树 ##

226. Invert Binary Tree (Easy)

翻转一棵二叉树

**思路与算法**

1.  这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子结点先开始翻转。
2.  如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。

1public TreeNode invertTree(TreeNode root) {
    2    if (root == null) return null;
    3    TreeNode left = root.left;  // 后面的操作会改变 left 指针，因此先保存下来
    4    root.left = invertTree(root.right);
    5    root.right = invertTree(left);
    6    return root;
    7}

## 5. 归并两棵树 ##

617. Merge Two Binary Trees (Easy)

Leetcode / 力扣

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

**解题思路**

1Input:
     2       Tree 1                     Tree 2
     3          1                         2
     4         / \                       / \
     5        3   2                     1   3
     6       /                           \   \
     7      5                             4   7
     8
     9Output:
    10         3
    11        / \
    12       4   5
    13      / \   \
    14     5   4   7

1public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    2    if (t1 == null && t2 == null) return null;
    3    if (t1 == null) return t2;
    4    if (t2 == null) return t1;
    5    TreeNode root = new TreeNode(t1.val + t2.val);
    6    root.left = mergeTrees(t1.left, t2.left);
    7    root.right = mergeTrees(t1.right, t2.right);
    8    return root;
    9}

# 题外话 #

这篇文章主要讲解了二叉树的一些基本概念，以及一些常见的递归算法题目，看起来挺简单的，但是让你写，你写得出来嘛？算法这种东西，要多练，动手实践，印象才深刻。所有的算法题目以及面试相关的，我都放在这个目录下，有空可以帮我 start 一下，谢谢。https://github.com/gdutxiaoxu/Android\_interview

留一下作业，打印出某个目录下的 .mp3 文件。

# 推荐阅读 #

[面试官：手写生产者消费者模型][Link 1]

[Gson 和 Kotlin data class 的避坑指南][Gson _ Kotlin data class]

[面试官系列 - LeetCode链表知识点&题型总结][- LeetCode]

如果你觉得对你有所帮助的话，可以关注我的公众号 徐公码字（stormjun94)，第一时间会在上面更新

![image][]

[format_png]: /images/20221119/71feb074779b42368e07499f8b53f538.png
[format_png 1]: /images/20221119/e8c42888cf9643b4b5a1b89ef2ffa301.png
[format_png 2]: /images/20221119/629af8eced7c4ae893705676e5120783.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95aadcdaed3bb707f2ed96306ea5462ea1e9ce20b71b6af158372d53644396998b78416e9&idx=1&mid=2247484909&scene=21&sn=e83b7b0e69fb630c4549ef9b23c79793#wechat_redirect
[Gson _ Kotlin data class]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95a8dcdaed39ba38ecae63e161cb7b8ab4ec7e5b583dc4a2da893362ef1549079ec9765e3&idx=1&mid=2247484877&scene=21&sn=1480d4b141dd84fb43a816d76f90bfdc#wechat_redirect
[- LeetCode]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95ac4cdaed3d2403d605ec09861f6796d082eab05d4f7f6c104d3d3e3f1d17ae4b7d10ecc&idx=1&mid=2247484804&scene=21&sn=d498f9d0e9b3811b26e86694ef66e9ba#wechat_redirect
[image]: /images/20221119/b4e06888dab542aba5f9a0f973b0bb62.png