【数据结构】二叉爆炸

按照惯例整点抽象的，贴上这篇博客的名字由来：

言归正传，本篇博客介绍二叉树的构造方式、前中后序遍历、层序遍历以及代码随想录中二叉树章节的相关题目：

代码随想录 (programmercarl.com)

一、啥是二叉树

1.二叉树是什么？

百度百科上的解释是这样的：

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 。

太长不看，简单来说，二叉树就是这个：

单亲爸爸带俩娃（划掉），一个根节点带着俩孩子。左边的孩子是“左子树”，右边的孩子是“右子树”。

下面是一些二叉树相关的定义，下面关于二叉树的算法题中可能会用到：

①节点：包含一个数据元素及若干指向子树分支的信息。

②节点的度：一个节点拥有子树的数目称为节点的度。

③叶子节点：也称为终端节点，没有子树的节点或者度为零的节点。

④分支节点：也称为非终端节点，度不为零的节点称为非终端节点。

⑤树的度：树中所有节点的度的最大值。

⑥节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层。

⑦树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度。

⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树。

⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。

⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树由原来根节点的各棵子树构成。

2.二叉树有啥用？

1. 数据存储和检索：二叉搜索树（BST）是一种常见的数据结构，用于存储和检索数据。在BST中，每个节点的左子树中的所有节点都小于该节点，右子树中的所有节点都大于该节点，这使得查找、插入和删除操作的平均时间复杂度为O(log n)，其中n是树中节点的数量。
2. 数据库索引：许多数据库系统使用二叉树或其变种（如B树、B+树）来加速数据检索。这些树结构允许在大量数据中快速找到所需的记录。
3. 文件系统：许多操作系统使用树状结构来组织文件和目录。文件系统中的每个目录都可以视为一个节点，其中包含文件和其他子目录。
4. 图形用户界面（GUI）：许多GUI工具包使用树形结构来组织用户界面元素。例如，菜单和文件资源管理器通常使用树形结构来表示层级结构。

3.特殊的二叉树！

满二叉树

所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上的二叉树。

这张图上的树就是一棵满二叉树。

完全二叉树

在满二叉树中，从最后一个结点开始，连续去掉任意个结点得到的二叉树。即最后一层所有节点靠左的二叉树。

如图所示：

二、咋遍历二叉树？

1. 深度优先搜索（前，中，后序遍历）

从根节点开始，沿着树的深度尽可能远的搜索树的分支。当达到树的最深处时，再回溯到上一级节点继续搜索，直到遍历完整棵树。

1. 前序遍历（Preorder Traversal）：以根节点、左子树、右子树的顺序遍历二叉树。
2. 中序遍历（Inorder Traversal）：以左子树、根节点、右子树的顺序遍历二叉树。
3. 后序遍历（Postorder Traversal）：以左子树、右子树、根节点的顺序遍历二叉树。

接下来我们就看看前中后序遍历的代码实现，此处均以leetcode上题目为模板。

前序遍历

递归遍历：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

迭代法遍历：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

中序遍历

递归遍历：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}

迭代法遍历：

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
    Stack<TreeNode> st = new Stack<>();
    if (root != null) st.push(root);
    while (!st.empty()) {
        TreeNode node = st.peek();
        if (node != null) {
            st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
            if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
            st.push(node);                          // 添加中节点
            st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
        } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
            st.pop();           // 将空节点弹出
            node = st.peek();    // 重新取出栈中元素
            st.pop();
            result.add(node.val); // 加入到结果集
        }
    }
    return result;
}
}

后序遍历

递归遍历：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}

迭代法遍历：

class Solution {
   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         
                               
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
   }
}

如何从中序和后序倒推出二叉树

先别急着看层序遍历，既然二叉树可以用这几种方式遍历，那么一定可以从这几种方式中倒推出二叉树的构造！

来看看这道题目：

首先复习一下中序遍历与后序遍历的遍历方式：

中序：左中右

后序：左右中

如果光看中序遍历数组，无法找到中间节点，光看后序遍历的数组，无法分割左右孩子，于是将两

种遍历方式结合起来，先从后序中找到中间节点的值，再将中序数组的左右孩子分开。

思路大概是：

第一步：如果数组大小为零的话，说明是空节点了。

第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中

序数组）

第五步：切割后序数组，切成后序左数组和后序右数组

第六步：递归处理左区间和右区间

接下来出场的是递归三部曲：

1. 首先确定递归函数返回值和参数：返回treenode，参数为两个数组及其区间。

2. 而后确定递归终止条件：当后序数组为空时，证明已经没有新的中间节点了，则返回空。

3. 最后确定单层递归逻辑：

在本题的单层递归中，我们需要做的事情稍显复杂：

1. 首先，我们需要从后序数组中找到最后一个值，即当前子树的根节点。
2. 而后，在中序数组中找到该节点，并保存其索引mid。
3. 以mid分割中序数组，找到左子树和右子树。
4. 分割后序数组，找到中序数组中左子树与右子树对应的左子树和右子树区间。
5. 将计算好的值传入下层递归中。
6. 最后返回根节点。

AC代码如下：

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length == 0 || inorder.length == 0)
            return null;
        return Build(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
    public TreeNode Build(int[] inorder, int inStart, int inEnd, int[] postorder, int posStart, int posEnd){
        if(posStart == posEnd){
            return null;
        }
        //后序遍历的最后一个值，即为当前子树的根节点
        int rootVal = postorder[posEnd - 1];
        TreeNode root = new TreeNode(rootVal);
        int mid;
        //从中序遍历数组中找到root结点
        for (mid = inStart; mid < inEnd; mid++){
            if(inorder[mid] == rootVal){
                break;
            }
        }

        //分割中序数组
        int lInStart = inStart; 
        int lInEnd = mid;
        int rInStart = mid + 1;
        int rInEnd = inEnd;

        //分割后序数组
        int lPosStart = posStart;
        int lPosEnd = posStart + (mid - inStart);
        int rPosStart = lPosEnd;
        int rPosEnd = posEnd - 1;
        
        //传入下层递归
        root.left = Build(inorder, lInStart, lInEnd,  postorder, lPosStart, lPosEnd);
        root.right = Build(inorder, rInStart, rInEnd, postorder, rPosStart, rPosEnd);

        return root;
    }  
}

2. 广度优先搜索（层序遍历）

从根节点开始，沿着树的宽度遍历树的节点。首先访问根节点，然后依次访问与根节点相邻的节点，直到遍历完整层的节点后再继续向下一层移动。

借用队列Queue来实现层序遍历，将每一层的内容放入队列中，在下一次遍历时，对队列中从头到

尾的每个元素进行检查，如果存在左右子节点，则入队，依次进行下去即可完成层序遍历。

例：对于如下二叉树，某一次的出队入队过程如下：

示例代码如下：

class Solution {
    public List<List<Integer>> ans = new LinkedList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return ans;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while(!que.isEmpty()){
            int len = que.size();
            List<Integer> ls = new LinkedList<>();
            
            while(len > 0){
                TreeNode temp = que.poll();
                ls.add(temp.val);
                if(temp.left != null){
                    que.add(temp.left);
                }
                if(temp.right != null){
                    que.add(temp.right);
                }
                len--;
            }
            ans.add(ls);
        }
        return ans;
    }
}

学完层序遍历可以一口气A完以下10题：

• 102.二叉树的层序遍历
• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度

我们选取一道典型的题目来看看：

这个题和116. 填充每个节点的下一个右侧节点指针两道题，用同一套代码直接解决了…

层序遍历真好用（喜）

用队列来进行层序遍历，再用一个list维护每一层的代码，在遍历完某一层后链接该层的next指针即可。

值得一提的是链接时用的while代码块，单独掏出来看看：

while(ls.size() > 1){
    Node pf = ls.removeLast();
    Node pb = ls.getLast();
    pb.next = pf;
}

首先把最后的节点保存，然后在get到倒数第二个节点，因为下一次遍历仍然会用到倒数第二个节

点，故而不能remove掉，再进行连接，结束条件是list中只剩下一个节点。

AC代码如下：

class Solution {
    public Node connect(Node root) {
        if(root == null){
            return root;
        }
        Queue<Node> que = new LinkedList<>();
        List<Node> ls = new LinkedList<>();
        que.add(root);
        while(!que.isEmpty()){
            int len = que.size();
            ls.clear();
            while(len > 0){
                Node tmp = que.poll();
                ls.add(tmp);
                if(tmp.left != null) que.add(tmp.left);
                if(tmp.right != null) que.add(tmp.right);
                len--;
            }
            while(ls.size() > 1){
                Node pf = ls.removeLast();
                Node pb = ls.getLast();
                pb.next = pf;
            }
        }
        return root;
    }
}

这个代码使用了List进行辅助，导致时间和空间都变得复杂了，唯一的好处是好理解，接下来登场的是优化代码~

public Node connect(Node root) {
    if(root == null){
        return root;
    }
    Queue<Node> que = new LinkedList<>();
    que.add(root);
    while (!que.isEmpty()) {
        int len = que.size();
        //前一个节点
        Node pre = null;
        while(len > 0){
            //出队
            Node node = que.poll();
            //如果pre为空就表示node节点是这一行的第一个，
            //没有前一个节点指向他，否则就让前一个节点指向他
            if (pre != null) {
                pre.next = node;
            }
            //然后再让当前节点成为前一个节点
            pre = node;
            //左右子节点如果不为空就入队
            if (node.left != null) que.add(node.left);
            if (node.right != null) que.add(node.right);
            len--;
        }
    }
    return root;
}

将内层的循环拿出来看：

定义一个pre节点，用于保存每次的节点，依次向后遍历，将每次出队的节点保存为node，若首次

插入，则将第一个node定义为pre，然后再进行后面的操作。

int len = que.size();
//前一个节点
Node pre = null;
while(len > 0){
    //出队
    Node node = que.poll();
    //如果pre为空就表示node节点是这一行的第一个，
    //没有前一个节点指向他，否则就让前一个节点指向他
    if (pre != null) {
        pre.next = node;
    }
    //再让当前节点成为前一个节点
    pre = node;
    if (node.left != null) que.add(node.left);
    if (node.right != null) que.add(node.right);
    len--;
}

三、结语

本篇博客介绍了树的基础知识以及树的各种遍历方式的应用，在接下来的学习中，还可能会接触到较为复杂的树，如二叉搜索树，平衡二叉树等。

本篇博客代码以及部分解析参考：

，则将第一个node定义为pre，然后再进行后面的操作。

int len = que.size();
//前一个节点
Node pre = null;
while(len > 0){
    //出队
    Node node = que.poll();
    //如果pre为空就表示node节点是这一行的第一个，
    //没有前一个节点指向他，否则就让前一个节点指向他
    if (pre != null) {
        pre.next = node;
    }
    //再让当前节点成为前一个节点
    pre = node;
    if (node.left != null) que.add(node.left);
    if (node.right != null) que.add(node.right);
    len--;
}

三、结语

本篇博客介绍了树的基础知识以及树的各种遍历方式的应用，在接下来的学习中，还可能会接触到较为复杂的树，如二叉搜索树，平衡二叉树等。

本篇博客代码以及部分解析参考：

代码随想录 (programmercarl.com)