【Java & 数据结构】初识二叉树

树型结构

什么是树形结构

树是一种非线性的数据结构, 也就是说它和我们前面学习的顺序表链表之类的不太一样. 那些数据结构要求中间的元素都只有一个前驱和后继, 而树型结构的中间元素则允许有多个后继.

例如下面这个就是一个树形结构

为什么叫这种结构为树形结构呢? 这是因为它的结构长的就像一颗倒过来的树, 最上面是树根, 最下面则是叶子.

下面我们看几个例子, 来认识一下树形结构的注意点

下面的这个结构, 就不是一个树形结构, 原因是其中间在同一层的节点, 是不可以相连的, 中间的节点只允许和上层节点和下层节点进行连接.

下面的这两个结构, 也不是树形结构, 原因是其有一些节点具有两个父亲节点, 也就是其有多个前驱, 这也是不允许的.

树的概念

节点的度: 节点的度指的是其含有子树的个数, 也可以看作是其后继的个数/子节点的个数. 如下所示, 下面这个节点的度是 4

树的度: 上面讲了节点的度, 那树的度则指的是它含有的所有节点的度的最大值. 比如下面的这个树的度是 4(上面蓝色数字为节点的度, 没有写则为 0)

叶子节点: 度为 0 的节点则是叶子节点, 例如下图蓝色节点都是叶子节点

父节点和子节点: 这两个节点是一个相对关系. 若一个节点有后继, 则这个节点则是后继节点的父节点. 若一个节点有前驱, 则这个节点是前驱节点的子节点. 例如下面这个 A 节点是另外 4 个节点的子节点, 下面的 4 个节点的父节点是 A 节点.

根节点: 最顶端的/没有父节点的节点就是根节点, 比较容易理解.

节点的层次: 根节点所处的层是第一层, 往下逐渐是第二层, 第三层…

树的高度: 节点的最大层次, 例如下面这棵树的高度就是 3

---

接下来的定义简单了解即可, 并不常见

分支节点: 顾名思义, 有分支的节点, 或者说是度不为 0 的节点

兄弟节点: 有相同父亲的节点为兄弟节点

堂兄弟节点: 父节点在同一层的节点为堂兄弟节点, 例如下图的 E 节点和 F 节点

节点的祖先: 从根节点到该节点分支上经过的所有节点就是该节点的祖先, 例如下图中的绿色节点就是 E 节点的祖先

子孙: 以当前节点为根, 下面的所有节点都是该节点的子孙, 例如下面 E 节点的子孙为所有的蓝色节点

森林: n棵树的集合就被叫做森林(n >= 0). 例如下面有两颗树, 那么它们组成的集合就被叫做一个森林

树的表示方法(了解)

树由于其复杂性, 表示方法比较繁琐并且也有多种方法, 我们这里就简单介绍一种孩子兄弟表示法.

孩子兄弟表示法指的就是每一个节点都只会存储其孩子和兄弟的引用, 其中存储的孩子一般是第一个孩子.

在 Java 中使用类来定义则如下所示

class Node{
    int value;
    Node firstChild;
    Node nextBrother;
}
1
2
3
4
5

下面是一个图示的例子, 可以看到, 其中 A 节点的 firstChild 就指向了第一个孩子节点 B, 然后由于其没有兄弟节点, 因此nextBrother为空.

接下来看 B 节点, 它有三个孩子, 它的firstChild则依旧是指向了第一个孩子 D, 然后nextBrother则指向它的后一个兄弟节点 C.

C 节点也是大体相同, firstChild指向孩子 G, 由于其没有下一个兄弟节点了, 因此nextBrother也为空

树的应用

树形结构最典型的引用就是我们的文件系统管理, 可以看到我们的文件系统, 都是一层一层的文件夹进行组织的, 如果将其展开, 就可以看作是一个树形结构

二叉树

二叉树是什么

二叉树, 顾名思义就是有两个分叉的树, 它对于所有节点都要求最多只能有两个分叉. 如下所示是一个二叉树的示例

其中, 它的左右节点是有次序的, 不能随意调换.

一些特殊的二叉树

首先就是满二叉树, 它指的就是一颗装满的二叉树. 那么什么情况下是装满呢? 我们上面知道一颗二叉树的所有节点最多都只能有两个分叉, 那么装满不就代表着所有的节点都有两个分叉吗?

大体虽然是这个意思, 但是我们需要注意的是, 其最下面一层的叶子节点是没有两个分叉的, 因为如果按照上面的这种要求递归进去, 这个树就没有尽头了.

下面就是一个满二叉树的例子

另一个要介绍的则是完全二叉树, 完全二叉树指的是将节点一层一层且从左到右的按照满二叉树的位置进行摆放所形成的二叉树.

例如我们按照一层一层且从左到右的次序, 对上面的这张满二叉树放置 11 个节点, 就可以形成下面这个完全二叉树

当然并不是说一定要放 10 个节点才能是完全二叉树, 只要是按照这样的次序摆放的, 都可以是完全二叉树.

此时可能有人要问了: 那假如说我按照这样的次序放了 15 个节点, 是不是又形成了一颗满的二叉树? 那它应该是什么二叉树呢?

实际上满二叉树, 就是完全二叉树的一种特殊情况, 因此这种时候它既是一颗完全二叉树, 也是一颗满二叉树.

二叉树的存储

二叉树实际上也是一种逻辑结构, 我们既可以通过顺序存储的方式也可以通过链式存储的方式来实现. 用人话说就是, 我们可以通过数组或者是类似链表引用的方式来实现二叉树这种结构.

由于使用链式存储的实现更加易懂, 因此初学二叉树我们就采用链式存储的方式来进行学习. 当然, 即使是采用链式存储, 也有许多不一样的存储方法, 其中涉及到的两种表示法就是孩子表示法和孩子双亲表示法.

使用 Java 代码来表示则如下所示

// 孩子表示法
class TreeNode{
    // 存储区域
    int val;
    // 左子树
    TreeNode left;
    // 右子树
    TreeNode right;
}

// 孩子双亲表示法
class TreeNode{
    // 存储区域
    int val;
    // 左子树
    TreeNode left;
    // 右子树
    TreeNode right;
    // 父节点
    TreeNode parent;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

可以看到, 孩子双亲表示法相较于孩子表示法就是多了一个引用指向自己的父节点. 但是由于涉及的东西越多, 那么代码就会越复杂. 因此初学的时候, 我们依旧是采用更加简单的孩子表示法来学习二叉树.

二叉树的基本操作

准备工作

首先我们先创建一个类, 并且创建一个内部类将刚刚提到的树节点创建好. 同时我们也和链表一样, 提供一个节点作为初始的引用, 当然这里的这个节点自然就是最顶层的根节点.

public class BinaryTree {
    // 节点定义
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { this.val = x; }
        
        TreeNode(int x, TreeNode left, TreeNode right){
            this.val = x;
            this.left = left;
            this.right = right;
            
        }
    }
    
    // 根节点
    TreeNode root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

接下来我们就需要通过实现一些二叉树的基本操作来更加深入的理解二叉树的这个结构, 而在实现二叉树的基本操作之前, 我们需要先创建一颗二叉树. 但是二叉树的创建并不像我们学习的前几个结构那么容易, 而树形结构对于我们来说也比较的陌生, 不像过去学习的那几个线性结构一样容易理解. 因此我们这里就先用一种比较原始的方式来创建一颗二叉树, 即手动的创建出一个一个的节点, 并且手动的将其连接起来

假如我们要创建下面这样的二叉树

那么我们的创建二叉树的代码就可以这样写

public void createBinaryTree() {
    // 创建节点
    TreeNode treeNode1 = new TreeNode(1);
    TreeNode treeNode2 = new TreeNode(2);
    TreeNode treeNode3 = new TreeNode(3);
    TreeNode treeNode4 = new TreeNode(4);
    TreeNode treeNode5 = new TreeNode(5);
    TreeNode treeNode6 = new TreeNode(6);

    // 手动创建一棵二叉树
    treeNode1.left = treeNode2;
    treeNode1.right = treeNode4;

    treeNode2.left = treeNode3;

    treeNode4.left = treeNode5;
    treeNode4.right = treeNode6;
    
    // 赋值
    this.root = treeNode1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

实现了一个简单的二叉树的创建, 接下来我们还需要学习一下二叉树的遍历, 它是我们后续书写二叉树其他基本操作的基石, 对于了解二叉树的递归处理非常重要, 因此我们先了解一下这个部分

二叉树的遍历

二叉树的遍历并没有和我们之前学习的线性结构一样那么的简单, 一条线往后走即可. 因此如果没有一些规定, 每个人想出的遍历方式都有可能会不一样, 因此我们如果想要学习二叉树的遍历, 首先就要了解一些二叉树的经典遍历方式.

二叉树的遍历, 首先不得不提的就是前序遍历, 中序遍历和后序遍历.

前序遍历指的是, 优先去处理根节点(为了简单理解, 我们后面将处理全部看作是打印操作), 其次再去找左节点, 最后再看右节点. 那么具体是什么意思呢? 我们直接通过一个例子来帮助理解

它首先是以上面这张图这样的次序进行遍历的, 其次它会在途中遇到一个一个的节点, 那么它的根->左->右则指的是. 它每进入一个节点, 就会把当前节点作为根节点, 先打印一下当前节点, 然后进入左边节点, 左边节点遍历完后, 就遍历右边, 遍历完右边后, 返回. 对于每一个节点都是如此

例如上面的这颗二叉树, 按照前序遍历的打印结果则是1 2 3 5 4 6. 实际上我们也可以看出, 它实际就是沿着我们的搜索路线来进行打印的, 遇到一个打印一个.

但是对于另外的两个遍历方式, 则有一些不太一样了. 它们两个的遍历方式如下

中序遍历: 根据左->根->右的方式遍历, 即把当前节点作为根节点, 先进入左边节点遍历, 遍历左边节点后, 再打印当前节点, 随后再遍历右边, 遍历完右边后, 返回.

后序遍历: 根据左->右->根的方式遍历, 即把当前节点作为根节点, 先进入左边节点遍历, 遍历左边节点后, 再遍历右边, 遍历完右边后, 最后打印当前节点, 随后返回.

也就是说我们可以将这个遍历分为三个操作: 1. 遍历左边 2. 遍历右边 3. 打印当前节点

而这三个遍历的区别就在于打印节点位于的次序不同, 其中遍历的次序固定, 都是先左后右. 但是打印节点的次序会在其中穿梭, 前序遍历中, 打印在两次遍历前进行. 中序遍历中, 打印在遍历中间进行. 后续遍历中, 打印则在最后进行.

对于上面的那一颗二叉树, 中序遍历和后续遍历的结果则如下所示

中序遍历: 3 2 1 5 4 6

后序遍历: 3 2 5 6 4 1

两个遍历的结果用于参考, 用于自己画图模拟来自行理解这两个遍历方法.

那现在我们粗略理解了一下这三个遍历的遍历顺序, 接下来我们就来通过代码来实现这三个遍历方法. 实际上, 如果对递归有一定理解的人, 在这个时候已经看出了这个代码是可以很轻松的使用递归来实现的.

为什么呢? 首先我们可以发现, 对于每一个节点, 我们的操作都是统一的, 以前序遍历为例子, 我们的每一个操作都是对当前节点打印, 随后遍历左节点和右节点. 那实际上遍历左节点的过程是什么呢? 实际上就是以左节点为一个新的根节点然后重复上述的操作而已.

那么我们的这个方法就可以以这样的结构进行分布

public void preOrder(TreeNode root) {

    // 打印
    System.out.print(root.val + " ");
    // 遍历左节点

    // 遍历右节点

}
1
2
3
4
5
6
7
8
9

那么上面我们说过, 遍历左节点, 实际上就是将当前节点的左节点作为根节点, 进行遍历, 那么不就是调用一下当前的这个方法, 并且把左节点传进去吗. 右节点也是同理的, 那么此时我们就可以把代码写出来了, 代码如下

public void preOrder(TreeNode root) {

    // 打印
    System.out.print(root.val + " ");
    // 遍历左节点
    preOrder(root.left);
    // 遍历右节点
    preOrder(root.right);
}
1
2
3
4
5
6
7
8
9

但是此时很明显, 如果去运行是一定会发生问题的. 一个问题是: 如果 root 为空怎么办? 另一个问题是: 在我们之前学习递归的时候说过, 一个递归必须有一个边界条件, 用于结束递归, 而这个递归很明显没有结束条件, 因此它是肯定有问题的.

实际上, 这两个问题, 就是一个问题, 也就是我们需要如何的去结束这个递归. 实际上如果想要去思考一个递归的边界条件怎么写, 我们可以通过最简单的一个方法, 就是直接去看一个具体的边界情况, 看如何解决就可以了. 比如下面这个例子

此时我们的节点 3 要往左遍历了, 会遇到空, 那么请问: 此时它可以打印吗? 很明显不行, 会抛出空指针异常. 那么此时我们就可以直接写一个条件判断, 判断当前的 root 是否为空, 如果为空, 则直接返回即可.

同时我们再思考返回后, 走到右边的情况, 很明显右边进去之后, 把右边节点当作 root 传进去过后, 依旧是空, 还是会返回, 因此我们的这个边界条件, 就是可以正常结束掉这个递归的一个边界条件. 那么此时我们就可以完善我们的代码了, 代码如下

public void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }

    // 打印
    System.out.print(root.val + " ");
    // 遍历左节点
    preOrder(root.left);
    // 遍历右节点
    preOrder(root.right);
}
1
2
3
4
5
6
7
8
9
10
11
12

然后我们尝试打印, 测试代码如下

public class Main {
    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();
        tree.createBinaryTree();
        tree.preOrder(tree.root);

    }
}
1
2
3
4
5
6
7
8
9

可以看到, 和我们上面讲解过的前序遍历的结果是一致的. 当然如果你此时还对前序遍历不太理解, 可以先自己创建几个二叉树, 同时使用这个代码来进行验证

写完了前序遍历, 实际上中序遍历和后续遍历就非常简单了. 我们说过, 这三个遍历的区别就在于, 打印的时机不同, 一个在遍历前打印, 一个在遍历中打印, 一个在遍历后打印. 而在我们刚刚书写代码的时候, 实际上我们就是先对这个顺序进行排序, 然后再书写的具体代码. 也就是说, 我们现在只要,把上面的代码按照对应遍历的顺序调整一下, 就可以得到正确的遍历代码了.

中序遍历的顺序是, 先遍历左边, 再打印根节点, 最后遍历右边. 同时也不要忘记了边界条件, 代码如下

public void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 遍历左边
    inOrder(root.left);
    // 打印节点
    System.out.print(root.val + " ");
    // 遍历右边
    inOrder(root.right);
}
1
2
3
4
5
6
7
8
9
10
11

那么后序遍历同理, 后序遍历的顺序是先遍历左边, 再遍历右边, 最后打印根节点, 因此代码如下

public void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 遍历左边
    postOrder(root.left);
    // 遍历右边
    postOrder(root.right);
    // 打印节点
    System.out.print(root.val + " ");
}
1
2
3
4
5
6
7
8
9
10
11

最后测试结果, 也是同样符合我们上面自己书写出来的结果的.

public class Main {
    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();
        tree.createBinaryTree();
        // 前序
        tree.preOrder(tree.root);
        System.out.println();
        // 中序
        tree.inOrder(tree.root);
        System.out.println();
        // 后序
        tree.postOrder(tree.root);

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

那么二叉树的三个基本的遍历, 我们就了解的差不多了. 实际上二叉树还有一个重要的遍历叫做层序遍历, 但由于这个遍历的思路和这三种不太一样, 因此这个我们就放到后面再来去介绍了.

---

在上面的代码中, 我们对于节点的处理都是打印, 那么接下来我们换一个要求, 我现在假如说需要你将其存储到一个 List 里面并且把结果返回过来, 那么此时我们应该怎么做?

public List<Integer> preOrder2(TreeNode root) {

}
1
2
3

假设我们还是进行前序遍历, 那么很明显, 处理顺序是不变的, 因此我们不用思考这方面的问题, 重点的问题在于, 如何将打印操作变为添加操作?

实际上在思考递归代码的时候, 我们可以先不考虑具体细节, 而是暂时的认为这个递归一定能够解决这个问题, 先设定一个框架.

那么根据这个思路, 我们现在就认为我们的这个方法是可以解决问题的. 那么我们的问题是什么? 就是返回以当前节点为根的前序遍历结果, 那么此时我们就可以认定为这个方法就可以返回对应的结果, 不用管具体实现. 那么此时我们就可以设计出一个大体的框架, 我们依旧是分为三步: 1. 添加根节点 2. 把左边的遍历结果添加进来 3. 添加右边的遍历结果. 那么我们就可以按照这个框架来先把代码写上去

public List<Integer> preOrder2(TreeNode root) {
    // 创建返回值
    List<Integer> list = new ArrayList<>();
    // 添加根
    list.add(root.val);
    // 添加左边结果
    list.addAll(preOrder2(root.left));
    // 添加右边结果
    list.addAll(preOrder2(root.right));
}
1
2
3
4
5
6
7
8
9
10

设定好了框架, 接下来就是处理剩余的细节问题. 也就是返回值和边界问题, 返回值很明显, 我们上面设定的这个方法的返回值什么? 就是以当前节点为根的前序遍历结果, 所以此时我们直接返回这个 list 就可以了.

而边界问题, 我们依旧是提出一个具体问题来进行研究. 此时如下图, 如果到了空, 我们应该如何返回? 是返回空吗?

很明显, 如果返回空且如果我们的addAll()方法将其放进去的话, 那么此时就可能会抛出空指针异常, 或者是使得我们的列表就会有一个 null 存储在里面. 这很明显不是我们想要的, 因此我们需要它此时返回一个空的列表, 这样既不会抛出空指针异常, 也不会添加一个 null. 那么既然是要返回一个空列表, 我们就在创建完列表后, 查看一下当前节点是否为空即可. 因为此时如果为空, 返回的列表就是刚创建的一个空列表

那么最终代码如下

public List<Integer> preOrder2(TreeNode root) {
    // 创建返回值
    List<Integer> list = new ArrayList<>();
    if(root == null){
        return list;
    }
    // 添加根
    list.add(root.val);
    // 添加左边结果
    list.addAll(preOrder2(root.left));
    // 添加右边结果
    list.addAll(preOrder2(root.right));

    return list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最后尝试运行发现结果正确

对于中序遍历和后序遍历, 思路大体相同, 可以尝试自己实现一下. 下面这里是三道相关的遍历题目, 可以参考上面的思路来做一下这三道题目

前序遍历: 二叉树的前序遍历

中序遍历: 二叉树的中序遍历

后序遍历: 二叉树的后序遍历

---

当然, 我们这里可以尝试一下, 在上面的边界返回值中, 如果返回 null 会发生什么事情.

public List<Integer> preOrder2(TreeNode root) {
    // 创建返回值
    List<Integer> list = new ArrayList<>();
    if(root == null){
        // 返回 null
        return null;
    }
    // 添加根
    list.add(root.val);
    // 添加左边结果
    list.addAll(preOrder2(root.left));
    // 添加右边结果
    list.addAll(preOrder2(root.right));

    return list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

运行发现, 抛出了空指针异常

原因是我们使用的是 ArrayList 实现的addAll()方法, 而在这个方法中, 它的第一步就是调用这个对象的toArray()方法

而如果我们返回 null, 在调用addAll()方法时, 参数c则是一个 null, 此时直接尝试调用一个方法自然就会抛出空指针异常.

求二叉树的节点个数

要求二叉树的节点个数, 方法还是比较多的, 我们可以回想一下我们在过去学习链表的时候是如何记录的, 是不是通过遍历 + 计数器来计数的? 那么自然我们这里也可以采取这样的方法.

但是由于我们现在学习的遍历都是以递归的方式来进行的, 因此如果需要采用这样的计数方法, 则需要创建一个全局的计数器, 也就是在方法外创建一个计数器. 此时代码如下所示

int size;
public void size(TreeNode root) {
    if (root == null) {
        return;
    }
    // 计数
    size++;
    // 遍历左边和右边
    size(root.left);
    size(root.right);
}
1
2
3
4
5
6
7
8
9
10
11

但是这样很明显和我们之前写的代码画风不符, 那么这一个问题是否也能够通过递归自身来实现呢?

对于一个二叉树操作是否能递归, 我们的核心就在于是否每一个节点都能够使用同样的处理方式. 很明显这一题是可以的, 我们能将其拆分为三个部分: 1. 计数根节点 2. 计数左树节点数 3. 计数右树节点数

那么此时我们假设进入了左树, 那么此时就将左树节点作为根, 继续执行上述操作, 直到遇到边界然后逐渐递归回来为止.

那么此时我们就可以设定一个方法, 其返回的结果是以当前节点为根的树的节点个数. 那么此时我们依照这个定义就可以写出这样的代码

public int size(TreeNode root) {
    // 计数根节点
    int rootSize = 1;
    // 计数左子树
    int leftSize = size(root.left);
    // 计数右子树
    int rightSize = size(root.right);
}
1
2
3
4
5
6
7
8

那么接下来我们依旧是处理细节问题, 也就是返回值和边界条件.

首先是返回值, 我们最初设定的就是以当前节点为根的树的节点个数, 那么自然我们就需要将这三个值相加并且返回.

其次就是边界条件, 由于已经进行过很多次了, 我们这里就不举具体例子了(当然, 如果你无法直接理解, 举一个具体的例子仍旧是一个非常好的选择). 这里我们直接思考如果遇到空节点它应该返回什么就行, 很明显对于一个空节点, 我们不应该去计数, 因此直接返回 0 即可.

那么最终代码如下

public int size(TreeNode root) {
    if (root == null) {
        return 0;
    }

    // 计数根节点
    int rootSize = 1;
    // 计数左子树
    int leftSize = size(root.left);
    // 计数右子树
    int rightSize = size(root.right);

    return rootSize + leftSize + rightSize;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

然后其实这些临时变量我们都可以创建, 而是直接返回, 那么代码就会变为下面这样

public int size(TreeNode root) {
    if (root == null){
        return 0;
    } 

    return size(root.left) + size(root.right) + 1;
}
1
2
3
4
5
6
7

求叶子节点的个数

求叶子节点的个数, 很明显好像和上面的有一点点类似, 甚至于大体框架都可以不用变. 上面求总节点个数我们采用的是: 1. 计数根节点 2. 计数左树节点数 3. 计数右树节点数. 那么既然是求叶子节点, 中间节点不用计数, 我们是不是就可以改成: 1. 处理根节点 2. 计数左树叶子节点数 3. 计数右树叶子节点数.

此时我们依旧是先设定方法的用途, 求什么就把我们的方法假定为可以干什么. 我们这里就设定方法可以返回以当前节点为根的叶子节点数. 那么此时我们可以书写代码如下

public int getLeafSize(TreeNode root) {
    // 计数左树叶子节点
    int leftLeafSize = getLeafSize(root.left);
    // 计数右树叶子节点
    int rightLeafSize = getLeafSize(root.right);
}
1
2
3
4
5
6

这里由于根节点我们暂定为不处理, 我们就先不写任何代码. 我们依旧是先处理细节问题, 返回值和边界条件.返回值那也很简单, 就是直接返回这两个变量的和即可, 但是对于边界条件, 则和我们之前的内容不太一样.

此时如果我们还是按照之前的, 判定 root 是否为空, 然后为空就返回 0 是否可以呢? 当然可以, 但是还不够. 因为我们的计数完全没有进行.我们应该有一个判定是否为叶子节点然后进行计数的地方, 那应该在哪判定?

实际上就在我们之前忽略的根节点的处理上面. 对于我们传入的根节点, 我们难道一定要直接递归它的左子树和右子树吗? 不一定, 当它如果是一个叶子节点的时候, 此时左子树和右子树必定为空, 进去了也没用什么作用, 那么我们应该如何设定呢? 我们实际上就可以判断一下, 当前节点的左子树和右子树是否为空, 如果为空, 此时我们直接返回 1 即可, 因为当前节点就是一个叶子节点.

同时这个对于根节点的处理, 即是对根节点的处理, 同时也是一个边界条件, 它能够直接处理掉叶子节点, 而不是让方法继续往两个空树进行递归.

那么此时我们的代码就可以修改如下

public int getLeafSize(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 根节点处理
    if (root.left == null && root.right == null) {
        return 1;
    }
    // 计数左树叶子节点
    int leftLeafSize = getLeafSize(root.left);
    // 计数右树叶子节点
    int rightLeafSize = getLeafSize(root.right);
    // 返回计数
    return leftLeafSize + rightLeafSize;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

当然我们这里也是可以不用两个变量, 直接在 return 中调用函数的. 我们这里就不演示了.

此时可能有人要问了: 我有了根节点处理这个边界条件, 是不是可以不要第一个边界条件了?

那我们可以先来测试一下, 如果我们删除掉这个部分, 尝试对我们之前创建好的二叉树进行计数, 看看会发生什么.

public int getLeafSize(TreeNode root) {
    //        if (root == null) {
    //            return 0;
    //        }
    // 根节点处理
    if (root.left == null && root.right == null) {
        return 1;
    }
    // 计数左树叶子节点
    int leftLeafSize = getLeafSize(root.left);
    // 计数右树叶子节点
    int rightLeafSize = getLeafSize(root.right);
    // 返回计数
    return leftLeafSize + rightLeafSize;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最终结果是, 抛出了一个空指针异常

那么是为什么呢? 实际上我们的这个边界条件, 也就只能够处理当前根节点是叶子节点的情况, 那如果有一个分支, 它有左树, 没有右树, 此时就会出现问题了. 那么此时在递归到右树的时候, 就会尝试调用这个空指针, 从而引发空指针异常.

获取二叉树第 k 层的节点数

这一个问题的方法参数略有不同, 因此我们先给出方法定义.

public int getKLevelNodeCount(TreeNode root, int k) {

}
1
2
3

那么此时我们可以发现, 此时我们为了求第 k 层节点的个数, 提供了一个参数 k. 那此时我们是不是就无法像前面一样往下递归了呢? 其实不是的, 我们首先来看一个例子

假设在下面的这棵树中, 我要求第三层的节点数, 也就是最下面的一层

那么此时很明显, 对于根节点 1 来说, k 就应该为 3. 但是我们尝试往他的子树走, 我们此时以 2 和 4 为根, 我们此就可以发现, 此时最下面的一层, 相对于这两个根来说不就是 2 吗, 不就是上一层的 k - 1吗?

也就是说, 即使有 k 存在, 我们依旧可以往下递归, 只要每一次让 k - 1 即可. 那么此时我们也可以确定另外一个事情, 这道题也是可以使用递归解决的, 那么既然可以采用递归, 我们就可以进行老套路了.

发现了可以使用递归解决问题, 那么此时我们就可以按照老套路, 定义出三个部分: 1. 处理根节点 2. 获取左子树 k - 1层的节点数 3. 获取右子树k - 1层的节点数.

那么此时有了上一题的经验, 我们不会直接忽略这个根节点的处理, 而是看看到底我们要处理什么. 答案也是非常明显的, 当 k 为 1 的时候, 代表已经到达了目标层数, 此时直接返回 1 即可, 这就是我们根节点的处理.

剩余的细节问题也是大差不差的, 返回值即求和返回, 边界条件则遇到空返回 0 即可.

最后按照上面的思路, 可以得出的代码如下

public int getKLevelNodeCount(TreeNode root, int k) {
    if (root == null) {
        return 0;
    }
    // k = 1, 返回
    if (k == 1) {
        return 1;
    }
    // 计算左子树
    int leftCount = getKLevelNodeCount(root.left, k - 1);
    // 计算右子树
    int rightCount = getKLevelNodeCount(root.right, k - 1);
    // 返回
    return leftCount + rightCount;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

获取二叉树的高度

这一题, 我们依旧是先看看能否使用递归来解决. 首先思考, 如果要求一棵树的高度, 我们是不是一定要找到最长的那一条分支, 而对于一个根节点来说, 无非就是从下面的两个分叉中选一条而已.

因此我们此时就可以得出思路, 要求二叉树的高度, 实际上就是求左子树和右子树的高度最大值.

那么此时我们就又可以回归老套路了, 定义出三个部分: 1. 处理根节点 2. 获取左子树高度 3. 获取右子树高度

那我们还是来看看这个根节点如何处理, 很明显似乎和我们之前的求节点一样, 如果当前节点的左右子树都是空的话, 则证明当前树的高度为 1, 直接返回 1 即可.

随后就是细节问题, 也就是返回值和边界条件. 首先就是返回值, 这里的返回值就和之前不一样了, 我们经过分析得知, 我们这里要求的是左右两个子树中的最大值, 因此我们这里首先要就要求出左右子树的最大值. 但是此时并没有结束, 因为我们这里求的只是子树的高度, 并没有包含自身的高度, 就比如下面的这个例子

对于节点 1 来说, 我算出了左右子树高度的最大值为 2. 那么此时我们可以直接返回 2 吗? 当然不行, 节点 1 本身自己也有一个高度, 我们也需要添加上去.

因此我们的返回值就是: 左右子树的高度最大值 + 1

那么边界条件也没有什么太大变化, 依旧是遇空返回 0 即可.

最终按照思路得出代码如下

public int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 处理根节点
    if (root.left == null && root.right == null) {
        return 1;
    }
    // 计算左子树高度
    int leftHeight = getHeight(root.left);
    // 计算右子树高度
    int rightHeight = getHeight(root.right);
    // 返回最大值 + 1
    return Math.max(leftHeight, rightHeight) + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这里有一道也是求高度的题目, 虽然它叫深度, 但是本质相同, 可以尝试提交一下(记得修改方法名称). 题目链接: 二叉树的最大深度

查找值为val的节点

这个查找的方法对于现在的我们来说应该是非常简单的了, 对于每一个节点来说, 要么这个值应该在根节点, 要么在左子树, 或者在右子树

因此我们依旧是分为三个部分: 1. 根节点处理 2. 搜索左子树 3. 搜索右子树

根节点的处理则是看当前根节点是否是我们要找的节点, 是就直接返回即可

返回值则是左子树和右子树任意一个不为空的结果, 当然如果两个都为空则返回空.

边界条件同上, 遇到空返回空.

按照上述思路, 我们书写的代码如下

public TreeNode find(TreeNode root, int val) {
    if (root == null) {
        return null;
    }
    // 根节点处理
    if (root.val == val) {
        return root;
    }
    // 搜索左子树
    TreeNode leftNode = find(root.left, val);
    // 搜索右子树
    TreeNode rightNode = find(root.right, val);

    // 如果 left 不为空, 返回 leftNode, 否则返回 rightNode
    return leftNode != null ? leftNode : rightNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

此时写了上面的这些操作, 那可能有人要问了: 你的方法返回值的意义设定, 一定是求什么就设定什么的吗?

实际上, 这也只是一个经验规律, 对于大部分简单的递归来说, 确实直接求什么就设定什么, 是基本上会奏效的. 因此这里为了降低学习成本, 上述的所有类似题目都直接这样设定返回值. 但是有没有一些情况, 是求什么设什么会失效的呢? 当然有, 例如这一篇文章中介绍的题目, 文章链接: 【二叉树】最近公共祖先.

那此时可能有人就觉得奇怪了: 那你这样让我求什么设定什么, 你不是坑了我吗?

实际上, 在上面的那篇文章中, 我们刚开始依旧是根据求什么设什么来进行设定的, 只不过在我们分析过后, 发现了这个返回值是不可行的, 因此通过再次分析得到了一个效果相同但是能够实现答案的返回值.

因此重点不在于能否一次性直接设定正确, 能一次性设定对那自然是最好的, 但是同时重点是学会分析返回值是否可行, 从而让我们在特殊情况中能够自行分析得出正确的设定. 只不过由于这部分是比较难的, 因此在现在还在初学二叉树的时候, 暂时可以忽视这部分的内容.

层序遍历

上面我们可以看到, 关于这种递归类型的操作, 我们基本都了解了. 因此接下来我们就来看一些不一样的操作. 也就是我们在之前就提到的层序遍历. 那么什么是层序遍历, 还记得我们了解特殊二叉树的时候说的完全二叉树的生成方法吗?

要生成一颗完全二叉树, 要一层一层, 从左到右的依次摆放节点才可以得到. 那么实际上, 层序遍历的遍历顺序, 就和生成一颗完全二叉树的生成顺序完全一致, 只不过对于层序遍历来说, 即使它不是一颗完全二叉树, 我们也是通过这样的顺序来进行遍历的.

那么此时我们有上面的经验, 此时自然我们就可能会往把它拆成根节点处理, 左子树处理, 右子树处理的方式. 但是很明显, 此时似乎不太一样了. 因为我们要的是一层一层的遍历, 和左右子树似乎并没有什么联系.

因为我们上面的处理方式, 都是递归左子树到最深的地方, 然后慢慢的往回

而这里则相当于是一层一层的走, 把一层探完了, 我们才会进入到下一层.

换句话说, 我们之前的思路, 包括我们最开始学习的前序中序和后序遍历, 都是以深度优先搜索为前提的. 为什么叫做深度优先搜索, 实际上根据我们上面的两张图也可以看得出, 它是优先去往一个点, 钻到最深的地方再逐步往回.

而我们这里的层序遍历, 则是另一种搜索方式, 这种搜索方式叫做广度优先搜索, 也就是我们会优先的将每一层都探索干净, 然后再去下一层.

那么很明显, 此时上面的思路就不可用了, 我们得思考一点新的思路来实现二叉树的层序遍历.

如果要层序遍历, 那么首先出去的就是节点 1, 随后跟在后面的就是节点 2 和 节点 4, 实际上就是节点 1 左树和右树的根节点, 因此我们需要在遍历节点 1 的时候, 就将其左右子树根节点存起来, 以备后用.

随后进行第二层的遍历, 那么就是节点 2 和节点 4, 那么此时我们就可以先把节点 2 和 节点 4 依次拿出来. 同时可以发现, 如果我们要进行第三层的遍历, 则也需要将它们的左右子树分别存起来. 如下图所示

此时后续的操作都是同理的, 然后我们就完成了一个层序遍历. 此时可能有人就发现了, 这右边的存储的出入都是先入先出啊, 那不就是一个队列吗?

确实如此, 我们的层序遍历, 就是可以借助于队列来实现的, 其实大体的思路我们上面都已经讲解的差不多了, 但是还有一些细节问题需要解决

首先一个细节问题就是我们的层序遍历这里是使用迭代+队列的方式执行的, 那么我们使用的循环的结束条件是什么呢?

很明显, 在左子树和右子树根节点为空的时候, 我们是不让它进队列的, 那么我们遍历最后一层的时候, 就一个节点也不会放, 那么自然遍历完的时候就不会有东西在队列里面了. 因此我们让循环的条件为队列是否为空即可

另一个细节问题就是, 如果我们的队列循环条件是判断其是否为空, 那么刚开始我应该如何开始这个循环呢?

根据我们上面的思路, 我们第一个遍历的是根节点, 因此我们在循环开始前, 把根节点放进去就可以了. 这样既解决了循环开始的问题, 也保证第一个遍历的是根节点.

总结一下核心步骤就是:

1. 创建一个队列用于存储节点
2. 把根节点放入队列
3. 循环遍历队列内的节点, 把每一个节点的非空左子树和右子树依次放入队列

那么现在思路就已经非常清晰了, 我们直接来看代码

public void levelOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 创建队列
    Queue<TreeNode> queue = new LinkedList<>();
    // 添加根节点
    queue.add(root);
    while (!queue.isEmpty()) {
        // 获取队列头节点
        TreeNode node = queue.poll();
        // 处理节点, 这里就简单打印
        System.out.print(node.val + " ");
        // 添加左子树
        if (node.left != null) {
            queue.add(node.left);
        }
        // 添加右子树
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

最后自己写一个测试代码, 测试其结果是否正确

public class Main {
    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();
        tree.createBinaryTree();
        tree.levelOrder(tree.root);

    }
}
1
2
3
4
5
6
7
8
9

可以看到, 结果就是我们之前创建二叉树的层序遍历结果

---

接下来我们就要对需求进行升级, 我现在不要你打印出结果, 而是要你把每一层的结果装到一个 List 里面, 最后返回所有 List. 实际上就是下面的这道题目, 题目链接: 二叉树的层序遍历

这题虽然核心思路和我们上面的层序遍历一致, 但是大的问题就在于它有返回值

它需要我们把每一层分开装入不同的 List. 那么问题就来了, 我们如何区分每一层呢?

回到我们上面的模拟思路, 我们来观察一下, 在遍历每一层前, 有什么特殊的情况是我们可以关注的

此时我们可以发现, 似乎每一次遍历一层前, 队列里面的节点数目, 实际上就是下一层的节点数目. 例如刚开始第一层只有一个节点, 此时队列里面就只有一个节点. 然后我们遍历完第一层后, 第二层有两个节点, 那么此时队列里面也只有两个节点, 第三层同理.

那么这是为什么呢? 其实很好理解, 我们每一次遍历, 都是将其节点的左右子树根节点放入, 那么自然我们如果遍历完了一层, 那么此时队列里面存储的就是所有的下一层元素.

此时我们就可以利用这个特性, 建立一个计数器, 初始为 1, 代表第一层节点数. 随后每弹出一个节点进行自减, 当其变为 0 的时候, 就重新计数, 计数的大小自然就是队列内部的节点数了.

那么此时有了思路, 实现代码如下

public List<List<Integer>> levelOrder(TreeNode root) {
    // 创建返回值
    List<List<Integer>> list = new ArrayList<>();
    if (root == null) {
        return list;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    // 创建计数器
    int count = 1;
    // 创建临时列表
    List<Integer> tmp = new ArrayList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
        
        // 添加节点, 计数器更新
        tmp.add(node.val);
        count--;
        // count == 0, 说明当前层已经遍历完毕, 添加临时列表, 重置临时列表, 重置计数器
        if (count == 0) {
            // 添加临时列表
            list.add(tmp);
            // 重置临时列表
            tmp = new ArrayList<>();
            // 重置计数器
            count = queue.size();
        }
    }
    return list;
}
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
35
36

层序遍历递归实现

上面我们学习了层序遍历, 那么此时可能有人就要问了: 之前我们的代码都是通过递归写的, 那么这个层序遍历, 是否也可以通过递归来实现呢?

实际上, 层序遍历当然也可以通过递归来实现, 但是思路是有一些不一致的. 我们这里就简单讲解一下如何实现

如果要通过递归来实现层序遍历, 那么不可避免的是, 我们一定会使用深度优先搜索, 假如按照我们之前的写法, 处理根节点, 处理左子树, 处理右子树的方式. 那么自然会先递归到左子树的最深处, 要想真正的和上面使用队列一样一层一层的遍历是不太现实的, 因此我们只能说在递归的过程中, 去给每一层进行处理.

例如我现在还是要求存入 List, 那么我如果使用递归, 我就会在递归到第二层的时候, 往第二层 List 放节点. 后续也是同理的, 如图所示

那么自然, 我们在遍历的时候就需要一个关键信息, 也就是层数, 因此在递归的过程中, 我们是需要将层数也一并提供的.

此时由于大体思路依旧是按照深度优先搜索的方式来进行的, 因此此时我们依旧可以按照之前的思路来进行分析

1. 根节点处理: 根节点的处理主要就是将对应层数的节点放到对应的 List 中去.
2. 左子树处理: 递归左子树, 传参时层数 + 1
3. 右子树处理: 递归右子树, 传参时层数 + 1
4. 边界条件: 为空停止
5. 返回值: 核心的递归函数没有返回值, 通过参数来进行返回值的存储

下面是一个参考代码

public List<List<Integer>> levelOrder(TreeNode root){
    // 创建返回值
    List<List<Integer>> list = new ArrayList<>();
    dfsLevelOrder(root, 1, list);
    return list;
}

public void dfsLevelOrder(TreeNode root, int level, List<List<Integer>> list){
    if (root == null){
        return;
    }
    // 根节点处理, 将对应层数的节点放到对应的 List 中
    // 但是要先保证 List 已经创建了
    if (list.size() < level){
        // 如果 size 小于 level, 说明这一层对应的 List 还没有创建
        list.add(new ArrayList<>());
    }
    list.get(level - 1).add(root.val);

    // 递归处理左右子树
    dfsLevelOrder(root.left, level + 1, list);
    dfsLevelOrder(root.right, level + 1, list);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

当然这个代码提交到上面的题目中, 也是可以通过的.

现在我们即实现了层序遍历的迭代版本, 也实现了其的递归版本, 那此时可能有人就要问了, 前面我们看的前序中序和后序遍历, 是否也有迭代版本的呢? 那么当然是有的, 接下来我们就来看, 如何通过迭代来实现前中后序的遍历.

迭代实现前序遍历

上面我们通过了一个队列, 来通过迭代实现了二叉树的层序遍历. 同理我们如果想要通过迭代来实现二叉树的前序遍历, 大概应该也是需要一个东西来存储节点的, 为什么呢? 我们来看图

假设我们正在前序遍历, 打印完了节点 1, 节点 2, 和节点 3, 那么此时, 如果是通过循环的方式, 我们没有办法回归到节点 2 去遍历它的右树. 因此需要一个存储来存储节点, 这是肯定的, 那么应该采用什么存储结构来存储呢?

那假如我现在的存储结构中, 存储着 1 2 3, 并且我继续往下遍历到了节点 3 的左子树, 判定到了为空, 到达了尽头.

那么此时很明显, 我们就需要取出刚刚存进去的节点3, 然后遍历完节点 3 的右子树后, 节点 3 也没有用了, 因此在这一次取出的时候, 直接删掉即可.

此时我们遍历右子树后, 又会遇到空, 此时很明显, 我们需要回到节点 2 了, 那么依旧是从我们的存储中拿出来, 然后回去遍历它的右子树.

此时可能有有人就发现了, 你这个结构, 不就是一个栈吗?

的确如此, 可以看到, 我们的节点 3 是最后一个进去的, 也是第一个出来的, 然后后续都是按照后入先出的原则, 在每一次遇到空节点后, 弹出节点.

那么如何开始这个循环呢? 和层序遍历一样先丢进去一个节点吗? 实际上是不行的, 因为层序遍历我们遍历的主要依靠就是队列里面的节点, 弹出一个就是遍历一个, 而这里我们遍历的主体实际上是一个指针, 我们这里定义其为 cur. cur 会从根节点出发, 一直往左走, 直到遇到空, 然后才是从栈中提取元素.

换句话说, 我们的循环应该由两个主体来决定, 一个是 cur 是不是空, 另一个则是栈是不是空. 当 cur 为空的时候, 证明左子树走完了, 而栈为空的时候则证明没有上层节点可以返回了, 此时变相的证明右子树也遍历完了.

那么此时我们按照上面的思路总结一下步骤:

1. 创建栈用于存储节点
2. 定义一个 cur 指针, 从根节点开始出发.
3. 当栈和cur都为不为空时, 循环:
   • 如果 cur 不为空, 放入节点, 同时向左走
   • 如果 cur 为空, 弹出栈顶节点, 同时向右走

那么我们这里先实现前序遍历, 打印处理节点的时机自然就是刚遇到节点的时候. 最后实现代码如下

// 前序遍历非递归
public void preOrderNonRecursion(TreeNode root){
    if(root == null) return;
    // 创建栈
    Stack<TreeNode> stack = new Stack<>();
    // 定义 cur 从根节点开始出发
    TreeNode cur = root;
    while(!stack.isEmpty() || cur != null){
        if(cur != null){
            System.out.print(cur.val + " ");
            // 不为空, 放入栈存储, 继续向左
            stack.push(cur);
            cur = cur.left;
        }else{
            // 为空, 返回上层遍历右侧
            cur = stack.pop();
            cur = cur.right;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

迭代实现中序遍历

实现了前序遍历, 接下来就是实现中序, 实际上前序遍历改为中序遍历, 还是比较好改的, 我们直接修改打印时机即可, 把打印节点的时机放到从栈中拿出根节点的时候即可

// 中序遍历非递归
public void inOrderNonRecursion(TreeNode root){
    if(root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while(!stack.isEmpty() || cur != null){
        if(cur != null){
            stack.push(cur);
            cur = cur.left;
        }else{
            cur = stack.pop();
            // 打印
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

因为当我们从栈中拿出节点的时候, 证明左子树已经遍历完了, 此时根据中序遍历顺序左->根->右, 那么正好这个时候就是打印的时候.

迭代实现后序遍历

后序遍历的非递归实现与前面两个就稍微有一些不同了, 为什么? 因为它的根节点最后打印, 因此我们直到一个节点的左右子树遍历完前, 都不能将其丢掉.

因此在遇到空的时候, 我们首先还不能将其丢掉, 而是要通过peek()来查看一下栈顶的节点. 然后再和之前一样去遍历它的右侧, 但是遍历右侧会有两个情况

1. 右侧为空, 证明右边已经遍历完了, 可以弹出
2. 右侧不为空, 从右侧节点继续遍历

// 后续遍历非递归
public void postOrderNonRecursion(TreeNode root){
    if(root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while(!stack.isEmpty() || cur != null){
        if(cur != null){
            stack.push(cur);
            cur = cur.left;
        }else {
            // cur向左走到了空, 遍历完了左子树, 此不能直接 pop 而是要先 peek
            if(stack.peek().right == null){
                // 右侧为空, 遍历完了, 可以弹出根节点打印了.
                cur = stack.pop();
                System.out.print(cur.val + " ");
            }else{
                // 否则从右侧继续遍历
                cur = stack.peek().right;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

但是此时, 这个代码依旧有一个Bug, 就是在往右节点走到最深处时, 会出错. 例如下面的这个情况

假设此时peek()到了栈顶元素右边的节点 2, 然后回到循环开头. 会把节点 2 放进去, 同时进入到 节点 2 的左侧, 也就是 null.

那么走到了 null 后, 代码就会去peek()栈顶元素的 right 是否为空, 很明显这里是的, 因此这里会直接打印 2, 并且弹出 2.

但是有一个严重的问题, 如图所示, cur 还是指着 2, 此时就会进入一个死循环, 一直重复上述过程.

那么如何解决呢? 我们额外弹出一次是否可行呢?

实际上也是不可以的, 因为即使我们额外弹出一次, 我们的 cur 仍然会指向 节点 1, 那么此时 cur 仍旧指向着一个元素, 又会重复更加前面的步骤.

那么是什么导致了死循环呢? 答案就是我们的程序不记得我们遍历过了什么节点, 而在这个后序遍历的实现中, cur 会多次的经过同一个节点, 一次是去查找它右子树的时候, 还有一次就是弹出的时候. 但是此时却没有任何标记告诉 cur 它此时是已经遍历完了还是没有遍历完, 此时自然就无法区分了.

因此我们就需要设立一个标记 prev , 告诉 cur 那些已经走过, 没有必要再走. 同时让这个 prev 去处理弹出的情况, 那么此时就不会弄混了.

public void postOrderNonRecursion(TreeNode root){
    if(root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;

    // prev用于存储上一个访问的节点
    TreeNode prev = null;

    while(!stack.isEmpty() || cur != null){
        if(cur != null){
            stack.push(cur);
            cur = cur.left;
        }else {
            // cur向左走到了空, 遍历完了左子树, cur去栈顶元素的右侧继续遍历
            // 但是如果右侧为空, 或者已经访问过 ,直接弹出
            if(stack.peek().right == null || prev == stack.peek().right){
                // 此时 cur 不再处理, 交给prev处理
                // prev拿到栈顶元素, 打印
                prev = stack.pop();
                // 此时, 当前栈顶节点的左右两侧都是空/遍历完了, 打印
                System.out.print(prev.val + " ");
            }else{
                cur = stack.peek().right;
            }
        }
    }
}
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

判断是否是完全二叉树

刚刚做了一道比较难理解的题目, 接下来我们来看一道比较简单的题目. 上面我们讲解层序遍历顺序的时候, 提到了其遍历的过程是和生成完全二叉树一致的, 那么这里我们是否可以参考它的思路来判断完全二叉树呢?

很明显是可以的, 我们只需要按照层序遍历的顺序去遍历一下整颗二叉树, 同时也把 null 也一起放进去, 看一下中间有没有出现 null 即可, 因为如果出现了 null, 则证明没有按照层序遍历的顺序来进行节点的放置, 自然就不是一颗完全二叉树, 如下所示

但是有一个问题, 我们如果会把 null 放进去, 那么即使它是一颗完全二叉树, 不也是会有 null 吗?

正因如此, 我们上面说的是判断中间是不是有 null 即可. 也就是节点和节点之间, 是否出现了 null. 那么如何判断这个 null 是节点和节点之间的呢?

也非常的简单, 如果我们遇到 null, 那么就停止遍历, 随后再去遍历一下整个队列, 看一下队列的后面有没有节点就行了. 如果没有节点, 而是全都是 null 的话, 那么就证明这是一颗完全二叉树.

有了思路, 我们就可以书写代码了, 代码如下

public boolean isCompleteTree(TreeNode root) {
    if (root == null) {
        return true;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    // 层序遍历
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        // 如果节点为空, 退出循环
        if (node == null) {
            break;
        }
        // 添加左子树
        queue.add(node.left);
        // 添加右子树
        queue.add(node.right);
    }

    // 遍历队列, 查看队列内是否还有节点
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node != null) {
            return false;
        }
    }

    return true;
}
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

二叉树的创建

了解二叉树的创建

上面经过了非常多二叉树相关操作的训练, 我们大体是对二叉树的结构已经有了一定理解了. 那么接下来我们就来介绍一下二叉树的创建.

关于二叉树的创建, 为什么不能一开始介绍, 实际上一部分是因为需要对二叉树的结构有一定理解才能创建. 另一部分则是涉及到创建方式的选择.

例如我现在就要求, 你给我写一个创建二叉树的方法, 那么你怎么写呢?

实际上是写不出来的, 因为没有具体的需求, 并且即使你给我了需求, 例如给我一个数组, 我同样也无法具体的给你一个二叉树, 因为创建的方式实在是太多样了, 你是要以层序遍历创建, 还是先序遍历创建等等问题.

因此我们需要对二叉树有了一定了解后, 才来学习这一部分是最合适的. 同时, 由于创建方式多样, 我们这里就只会介绍两种创建方式, 一个是通过前序遍历和中序遍历创建, 另一个则是通过中序遍历和后序遍历创建.

此时可能有人就要问了: 为什么是前序遍历和中序遍历一起才能创建? 前序遍历自己不行吗?

实际上, 还真的不行, 例如我们举一个例子, 假如我现在有一个前序遍历序列1 2 3, 那么请问此时我可以确定一颗二叉树吗? 答案是不行, 这仅仅 3 个数字的前序序列, 我们就可以列出如下三种情形的二叉树(其实还有但是我们不列举了, 只需要知道前序遍历无法确定唯一的二叉树即可)

后序遍历也是同理的, 也是无法确认一棵二叉树.

那此时可能有人有要问了: 那前序遍历和后序遍历不行吗? 为什么一定要和中序遍历一起呢?

实际上都需要和中序遍历一起, 则证明中序遍历有其特性, 那么是什么特性呢? 还记得我们是如何生成中序遍历的吗? 是按照左->根->右的方式遍历的. 可以看到根节点是在中间的, 那么也就是说, 在一个序列中, 如果我知道了某一个位置它是一个根节点, 那么此时我依照着中序遍历, 就可以区分出它的左右子树分别是什么.

而前序遍历和后序遍历, 则是将根分别放在了最前面和最后面, 都是用于提供根节点信息的. 因此前/后序遍历和中序遍历就是可以用于确定一棵二叉树的.

那此时可能有人还有问题: 那假如以前序遍历为例子, 我不也是根->左->右吗, 那我不也可以区分出左和右吗? 实际上这点是并不可行的, 依旧是以上面的1 2 3序列为例子

那么此时假设我就知道根节点是 1, 我能否确认一棵树呢? 不行, 因为没有人说右一定不是空, 万一右是空呢? 那么此时左可能就有两个数2 3, 同理, 也有可能左边是空. 后序遍历也是同理的, 因此只有前序和后序, 是无法确认左右子树的节点的.

前序遍历和中序遍历创建二叉树

接下来我们通过一个例子来演示, 如何手动的通过一个前序遍历序列和中序遍历序列创建一个二叉树.

假设前序遍历序列为: 3 9 20 15 7, 中序遍历序列为: 9 3 15 20 7

我们上面也说过, 中序遍历是能够通过根节点来确认左右子树分别有什么元素的. 那么我们如何去找到根节点呢? 很明显对于前序遍历来说, 第一个节点就是根节点, 那么此时我们就可以将其划分为如下情况

那么此时我们就知道了 3 是根节点, 左子树有 9, 右子树有 15 20 7 三个元素.

那么接下来我们如何继续操作呢? 我们先想象假如前序遍历递归进入了左子树, 那么此时是不是 9 就会成为当前的根节点? 那么实际上我们此时就复刻上面的操作就可以了.

但是由于这里左子树只有 9 因此也没有什么可以说的, 我们就看右树的情况. 可以看到, 遍历完 9 后紧接着的就是 20. 那么此时我们依旧是将其当作根节点, 在中序遍历的分离结果中, 继续对其左右子树进行分离, 那么就可以得到如下情况

此时可以看到, 实际上就已经形成了一颗二叉树, 这就是如何使用前序遍历和中序遍历生成二叉树的过程. 接下来我们就需要通过代码来实现一下这个步骤. 也就是这一个题目: 从前序与中序遍历序列构造二叉树

但是应该如何实现呢?

很明显, 根据我们上面的过程, 我们可以分析出, 首先我们需要通过一个指针遍历前序遍历. 并且每遍历到一个元素, 就需要将其中序遍历序列分为两块分别递归进行构建. 当最终递归的只剩下一个节点的时候, 则证明当前子树已经构建完成了.

那么首先我们根据上面的分析, 设定返回值为对应中序遍历区间构建出的根节点, 同时为了能够表示区间, 我们需要两个指针来进行表示, 因此我们需要两个指针来代表区间. 并且还需要一个指针用于遍历前序序列

那么我们刚开始就有如下定义

class Solution {
    // 前序遍历指针
    int p = 0;
    // 方法封装
    public TreeNode build(int[] preorder, int[] inorder, int start, int end){

    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, inorder.length);
    }
}
1
2
3
4
5
6
7
8
9
10
11

那么接下来, 实际上也是我们的深搜分析

1. 根节点处理:

   • 如果 start 等于 end, 那么此时创建两个指针指向的共同节点并且返回.

   • 如果 start 小于 end, 那么就在中序遍历序列中, 找到前序遍历序列指针指向的元素, 同时创建根节点, 用于后续的左右子树创建.

2. 左子树处理: 根据左侧区间, 创建左子树

3. 右子树处理: 根据右侧区间, 创建右子树

4. 返回值: 返回根节点

5. 边界条件: 如果 start 大于 end, 返回 null

class Solution {
    // 前序遍历指针
    int p = 0;
    // 方法封装
    public TreeNode build(int[] preorder, int[] inorder, int start, int end){
        // 边界条件
        if(start > end) return null;

        // 根节点处理1
        if(start == end){
            p++;
            return new TreeNode(inorder[start]);
        } 

        // 根节点处理2
        int target = 0;
        for(int i = start; i <= end; i++){
            if(inorder[i] == preorder[p]){
                target = i;
                break;
            }
        }
        
        TreeNode root = new TreeNode(inorder[target]);
        p++;
        // 处理左右子树
        root.left = build(preorder, inorder, start, target - 1);
        root.right = build(preorder, inorder, target + 1,end);

        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, inorder.length - 1);
    }
}
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
35
36

中序遍历和后序遍历创建二叉树

看完了前序遍历和中序遍历的创建, 我们也来看一下后序遍历和中序遍历的创建. 其实本质上都是一样的, 只不过后序遍历表示根节点是从后往前来的, 并且由于遍历顺序是左->右->根, 因此从后往前, 依次是根节点, 其次是右子树, 最后才是左子树

我们就以一个例子看一下过程, 假设后序遍历序列为: 9 15 7 20 3, 中序遍历序列为: 9 3 15 20 7

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

首先就是从后往前遍历, 然后根据中序遍历序列来区分左右子树

后续同上操作, 由于和前序区别不大, 我们简单看一下即可

同时, 实际上代码的差别也是很小的, 一个区别就是指针是从后往前走的, 这个从我们的手动操作上也可以看出来. 同时还有另外一个区别, 由于后序遍历顺序是左->右->根, 因此在从后往前遍历创建子树时, 应该先创建右子树, 后创建左子树.

由于与前序遍历序列和中序遍历序列差别不大, 因此不再细讲, 这里直接提供一份参考代码, 其中的区别使用注释标出. 参考代码如下

class Solution {
    // 后序遍历指针
    int p;
    // 参数修改
    public TreeNode build(int[] inorder, int[] postorder, int start, int end){
        if(start > end) return null;

        // p++ 都改为了 p--
        if(start == end){
            p--;
            return new TreeNode(inorder[start]);
        } 

        int target = 0;
        for(int i = start; i <= end; i++){
            if(inorder[i] == postorder[p]){
                target = i;
                break;
            }
        }
        
        TreeNode root = new TreeNode(inorder[target]);
        p--;

        // 左右子树顺序调换
        root.right = build(inorder, postorder, target + 1,end);
        root.left = build(inorder, postorder, start, target - 1);

        return root;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 这里初始化一下后序遍历指针
        p = postorder.length - 1;
        return build(inorder, postorder, 0, inorder.length - 1);
    }
}
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
35
36