二叉树的刷题笔记
发表Note大约5452个字

二叉树的刷题笔记

最近在代码随想录上学习各种算法并做了一些记录

二叉树的种类

在我们解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树。

满二叉树

定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。 也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

如图：

完全二叉树

定义：完全二叉树是由满二叉树而引出来的，对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

如图：

二叉搜索树

定义：二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

  1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉查找树；

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为 O(logn) 。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

如图：


平衡二叉搜索树

定义：平衡二叉搜索树（英语：Balanced Binary Search Tree）是一种结构平衡的二叉搜索树，它是一种每个节点的左右两子树高度差都不超过1的二叉树。它能在 O(logn) 内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树

常见的平衡二叉搜索树有：

  • AVL树
  • 红黑树

如图：

最后一棵树左子树高度为2，右子树高度为0，高度差的绝对值大于1了

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储。

那么链式存储方式就用指针， 顺序存储的方式就是用数组。

顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

链式存储如图：

顺序存储如图：

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树的遍历方式

二叉树主要有两种遍历方式：

  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。

    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）

  2. 广度优先遍历：一层一层的去遍历。

    • 层次遍历（迭代法）

这两种遍历是图论中最基本的两种遍历方式

做二叉树相关题目时，我们经常使用递归方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。

栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。

而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

二叉树的定义

public class TreeNode {
    int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
      }
}

二叉树的深度优先遍历

递归法

对应LeetCode的题目：

如果对递归不清楚的可以先去看一段视频了解一下：递归函数

写递归的三要素：

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

以前序遍历为例：

  1. 确定递归函数的参数和返回值，因为要打印出前序遍历节点的数值，所以参数里需要传入List来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：
public void preorder(TreeNode root, List<Integer> result)
  1. 确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：
if(root == null) {return;}
  1. 确定单层递归的逻辑：前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：
    result.add(root.val);
    preorder(root.left, result);
    preorder(root.right, result);

Tips：前中序遍历需将result.add(root.val)写到正确的位置

前序遍历

// 前序遍历·递归·LC144_二叉树的前序遍历
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);
    }
}

中序遍历

// 中序遍历·递归·LC94_二叉树的中序遍历
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);
    }
}

后序遍历

// 后序遍历·递归·LC145_二叉树的后序遍历
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);             // 注意这一句
    }
}

迭代法

对应LeetCode的题目：

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

前序遍历

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子，这样出栈的时候才是中左右的顺序。

动画示意如下：


代码如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
         //建List用来存放栈弹出的结果
        List<Integer> result = new ArrayList<Integer>();   
        if(root == null) return result;
        //建栈
        Stack<TreeNode> stack = new Stack<>();  
        //将根节点root入栈
        stack.push(root);                       
        while(!stack.isEmpty()){       
             //将出栈的值用node记录下来，并保存到result中        
            TreeNode node = stack.pop();       
            result.add(node.val);         
            //判断被记录的node右子树值是否为空,将此节点的右子树的值入栈  
            if(node.right != null) stack.push(node.right);         
            //同右子树逻辑一样
            if(node.left != null) stack.push(node.left);
        }
        return result;                        
    }
}

中序遍历

为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：

  1. 处理：将元素放进result数组中
  2. 访问：遍历节点

分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

动画示意如下：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            //用来访问最底层
           if (cur != null){       
            //将访问的节点放入栈中
               stack.push(cur);    
               cur = cur.left;      //左
           }else{
               //从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
               cur = stack.pop();   
               result.add(cur.val);               //中
               cur = cur.right;                      //右
           }
        }
        return result;
    }
}

后序遍历

后序遍历与前序遍历的关系：

  • 前序遍历：中左右
  • 后序遍历：左右中

如果从前序遍历得到后序遍历，首先调换前序遍历的左，右的位置，得到中，右，左，然后再翻转，得到左，右，中。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
         //建List用来存放栈弹出的结果
        List<Integer> result = new ArrayList<Integer>();   
        if(root == null){
            return result;
        }
         //建栈
        Stack<TreeNode> stack = new Stack<>();  
         //将根节点root入栈
        stack.push(root);  
        while(!stack.isEmpty()){             
             //将出栈的值用node记录下来，并保存到result中  
            TreeNode node = stack.pop();       
            result.add(node.val);
            //注意先左，后右               
            if(node.left != null) stack.push(node.left);
            if(node.right != null) stack.push(node.right);
        }
        //处理完后,结果集中的结果是中右左，对结果进行翻转后得到左右中
        Collections.reverse(result);            
        return result;                         
    }
}

二叉树的广度优先遍历

二叉树的层序遍历

接下来我们再来介绍二叉树的另一种遍历方式：层序遍历。

102.二叉树的层序遍历

力扣题目链接

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

思路：

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

动画示意如下：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root){
        //用一个二维数组来接受最终结果
        List<List<Integer>> resList = new ArrayList<List<Integer>>();  
        //创建一个队列用来存放二叉树节点
        Queue<TreeNode> que = new LinkedList<TreeNode>();    
        //判断是否为空
        if(root == null) return resList;  
        //将根节点入队
        que.offer(root);                                       
        while(!que.isEmpty()){
             //创建数组来存放出队的值
            List<Integer> itemList = new ArrayList<Integer>();  
            //记录队列的大小
            int len = que.size();     
            //控制队列的大小从而来控制出队的数，达到同一层的数正确的记录到一个数组中              
            while(len > 0){                                     
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);
                if(tmpNode.left != null) que.offer(tmpNode.left);
                if(tmpNode.right != null) que.offer(tmpNode.right);
                //每出队一个值，队列大小-1，
                len--;                                          
            }
            resList.add(itemList);
        }
        return resList;
    }
}

107.二叉树的层次遍历 II

力扣题目链接

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路：

相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。

class Solution { 
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 利用链表可以进行 O(1) 头部插入, 这样最后答案不需要再反转
        LinkedList<List<Integer>> ans = new LinkedList<>();
        Queue<TreeNode> que = new LinkedList<TreeNode>();          
        if(root != null) que.offer(root);                            
        while(!que.isEmpty()){
            List<Integer> temp = new ArrayList<Integer>();  
            int len = que.size();                               
            for(int i = 0; i < len; i++){
                TreeNode node =que.poll();
                temp.add(node.val);
                if(node.left != null) que.offer(node.left);
                if(node.right != null) que.offer(node.right);
            }
            ans.addFirst(temp);     //将新遍历的结果插入到链表头部
        }
        return ans;
    }
}

199.二叉树的右视图

力扣题目链接

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

思路：

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Queue<TreeNode> que = new LinkedList<>();
        if(root == null) return list;
        que.offer(root);
        while(!que.isEmpty()){
            int levelSize = que.size();
            for(int i = 0; i < levelSize; i++){
                TreeNode pollNode = que.poll();
                //对栈的循环只将每层中的最后一个元素加入结果集就行，实在不理解可以画一个二叉树模拟一遍
                if(i == levelSize - 1) list.add(pollNode.val);
                if(pollNode.left != null) que.offer(pollNode.left);
                if(pollNode.right != null) que.offer(pollNode.right);
            }
        }
        return list;
    }
}

637.二叉树的层平均值

力扣题目链接

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

思路:

本题就是层序遍历的时候把一层求个总和在取一个均值。

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<Double>();
        Queue<TreeNode> que = new LinkedList<>();
        if(root == null) return list;
        que.offer(root);
        while(!que.isEmpty()){
            int levelSize = que.size();
            //定义一个double类型的变量存放每层的平均值
            double levelSum = 0.0;
            for(int i = 0; i < levelSize; i++){
                TreeNode pollNode = que.poll();
                //将弹出队列的元素加到变量中
                levelSum += pollNode.val;
                if(pollNode.left != null)  que.offer(pollNode.left);
                if(pollNode.right != null) que.offer(pollNode.right);
            }
            list.add(levelSum / levelSize);
        }
        return list;
    }
}

429.N叉树的层序遍历

力扣题目链接

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

思路:

这道题依旧是模板题，只不过一个节点有多个孩子了

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<Node> que = new LinkedList<>();
        if(root == null) return ans;
        que.offer(root);
        while(!que.isEmpty()){
            int levelSize = que.size();
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < levelSize; i++){
                Node pollNode = que.poll();
                //将从队列弹出的孩子节点依次入队
                for(Node node : pollNode.children) que.offer(node);
                list.add(pollNode.val);
            }
            ans.add(list);
        }
        return ans;
    }
}

515.在每个树行中找最大值

力扣题目链接

您需要在二叉树的每一行中找到最大的值。

思路：

层序遍历，取每一层的最大值

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        if(root == null) return ans;
        que.offer(root);
        while(!que.isEmpty()){
            int levelSize = que.size();
            int levelMax = Integer.MIN_VALUE;
            for(int i = 0; i < levelSize; i++){
                TreeNode pollNode = que.poll();
                //利用max函数判断levelMax的值和出队的值谁大
                levelMax = Math.max(levelMax,pollNode.val);
                if(pollNode.left != null) que.offer(pollNode.left);
                if(pollNode.right != null) que.offer(pollNode.right);
            }
            ans.add(levelMax);
        }
        return ans;
    }
}

116.填充每个节点的下一个右侧节点指针

力扣题目链接

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

思路：

本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

迭代：

class Solution {
    public Node connect(Node root) {
        if(root == null) return root;
        Deque<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int n = queue.size();
            for(int i = 0; i < n; i++){
                Node node = queue.pop();
                 if(i != n-1) node.next = queue.peek();
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
        }
        return root;
    }
}

递归：

class Solution {
    public Node connect(Node root) {
        if(root == null) return null;
        DFS(root);
        return root;
    }

    public void DFS(Node root){
        //递归退出条件，需要用到父节点来操作.next指向右邻居，所以最后一次递归执行是当root到叶子结点的上一层对叶子结点进行操作
        if(root.left == null || root.right == null){
            return;
        }
        //root的左孩子肯定有右邻居
        root.left.next = root.right;
        //如果父亲节点有右邻居，那么父节点root的右孩子一定也有右邻居
        if(root.next != null){
            root.right.next = root.next.left;
        }
        //前序遍历
        DFS(root.left);
        DFS(root.right);
    }
}

117.填充每个节点的下一个右侧节点指针II

力扣题目链接

思路：

这道题目说是二叉树，但116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道

class Solution {
    public Node connect(Node root) {
        if(root == null) return root;
        Deque<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int n = queue.size();
            for(int i = 0; i < n; i++){
                Node node = queue.pop();
                 if(i != n-1) node.next = queue.peek();
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
        }
        return root;
    }
}

104.二叉树的最大深度

力扣题目链接

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

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

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

思路：

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，如图所示：

递归：

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        //计算左子树深度
        int leftHight = maxDepth(root.left);
        //计算右子树深度
        int rightHight = maxDepth(root.right);
        //从左子树和右子树深度中选一个最大的值和当前节点+1，并且返回maxHight
        return Math.max(leftHight,rightHight) + 1;
    }
}

迭代：

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode pollNode = queue.poll();
                if(pollNode.left != null) queue.offer(pollNode.left);
                if(pollNode.right != null) queue.offer(pollNode.right);
            }
            depth++;
        }
        return depth;
    }
}

111.二叉树的最小深度

力扣题目链接

相对于 104.二叉树的最大深度 ，本题还也可以使用层序遍历的方式来解决，思路是一样的。

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            depth++;
            for(int i = 0; i < size; i++){
                TreeNode pollNode = queue.poll();
                //如果当前节点的左右孩子都为空，直接返回最小深度
                if(pollNode.left == null && pollNode.right == null) return depth;
                if(pollNode.left != null) queue.offer(pollNode.left);
                if(pollNode.right != null) queue.offer(pollNode.right);
            }
        }
        return depth;
    }
}

二叉树的刷题笔记

https://poluk2001.github.io/2023/05/share-BinaryTree.html

作者

Poluk

发布于

2023-05-25

更新于

2023-09-05

许可协议

#

评论

最新文章

标签

Git1
Github1
LeetCode1
分享1
思绪1
总结1
生活1
算法1
美学1
计算机基础1
计算机组成与设计1
阿尔贝·加缪1
×