当前位置： 首页 > article >正文

04树 + 堆 + 优先队列 + 图（D1_树（D2_二叉树（BT）（D2_刷题练习）））

article 2025/3/6 15:55:53

目录

一、二叉树遍历问题

1. 二叉树的前序遍历（简单）

1.1 题目描述

1.2 解题思路

方法一：递归（推荐使用）

方法二：非递归（扩展思路）

2. 二叉树的中序遍历（中等）

2.1 题目描述

2.2 解题思路

方法一：递归（推荐使用）

方法二：非递归（扩展思路）

3. 二树的后序遍历（简单）

3.1 题目描述

3.2 解题思路

方法一：递归（推荐使用）

方法二：非递归（扩展思路）

4. 求二叉树的层序遍历

4.1 题目描述

4.2 解题思路

方法一：非递归（推荐使用）

方法二：递归（扩展思路）

5. 从前序与中序遍历序列构造二叉树（done）

5.1. 题目描述

5.2. 解题思路

方法一：递归

方法二：迭代

6. 二叉树的层序遍历 II（done）

6.1. 题目描述

6.2. 解题思路

方法一：广度优先搜索

一、二叉树遍历问题

1. 二叉树的前序遍历（简单）

1.1 题目描述

1.2 解题思路

方法一：递归（推荐使用）

import java.util.*;
public class Solution {
    public void preorder(List<Integer> list, TreeNode root){
        //遇到空节点则返回
        if(root == null)
            return;
        //先遍历根节点
        list.add(root.val);
        //再去左子树
        preorder(list, root.left);
        //最后去右子树
        preorder(list, root.right);
    }
     
    public int[] preorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList();
        //递归前序遍历
        preorder(list, root);
        //返回的结果
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}

方法二：非递归（扩展思路）

Java实现代码：

import java.util.*;
public class Solution {
    public int[] preorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        Stack<TreeNode> s = new Stack<TreeNode>();
        //空树返回空数组
        if(root == null) 
            return new int[0];
        //根节点先进栈
        s.push(root); 
        while(!s.isEmpty()){
            //每次栈顶就是访问的元素
            TreeNode node = s.pop(); 
            list.add(node.val);
            //如果右边还有右子节点进栈
            if(node.right != null) 
                s.push(node.right);
            //如果左边还有左子节点进栈
            if(node.left != null) 
                s.push(node.left);
        }
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}

2. 二叉树的中序遍历（中等）

2.1 题目描述

2.2 解题思路

方法一：递归（推荐使用）

import java.util.*;
public class Solution {
    public void inorder(List<Integer> list, TreeNode root){
        //遇到空节点则返回
        if(root == null) 
            return;
        //先去左子树
        inorder(list, root.left); 
        //再访问根节点
        list.add(root.val); 
        //最后去右子树
        inorder(list, root.right); 
    }
    
    public int[] inorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        //递归中序遍历
        inorder(list, root); 
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}

方法二：非递归（扩展思路）

Java实现代码：

import java.util.*;
public class Solution {
    public int[] inorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        Stack<TreeNode> s = new Stack<TreeNode>();
        //空树返回空数组
        if(root == null) 
            return new int[0];
        //当树节点不为空或栈中有节点时
        while(root != null || !s.isEmpty()){ 
            //每次找到最左节点
            while(root != null){ 
                s.push(root);
                root = root.left;
            }
            //访问该节点
            TreeNode node = s.pop(); 
            list.add(node.val); 
            //进入右节点
            root = node.right; 
        }
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}

3. 二树的后序遍历（简单）

3.1 题目描述

3.2 解题思路

方法一：递归（推荐使用）

import java.util.*;
public class Solution {
    public void postorder(List<Integer> list, TreeNode root){
        //遇到空节点则返回
        if(root == null) 
            return;
        //先去左子树
        postorder(list, root.left); 
        //再去右子树
        postorder(list, root.right); 
        //最后访问根节点
        list.add(root.val); 
    }
    
    public int[] postorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        //递归后序遍历
        postorder(list, root); 
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}

方法二：非递归（扩展思路）

Java实现代码：

import java.util.*;
public class Solution {
    public int[] postorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode pre = null;
        while(root != null || !s.isEmpty()){ 
            //每次先找到最左边的节点
            while(root != null){ 
                s.push(root);
                root = root.left;
            }
            //弹出栈顶
            TreeNode node = s.pop(); 
            //如果该元素的右边没有或是已经访问过
            if(node.right == null || node.right == pre){ 
                //访问中间的节点
                list.add(node.val); 
                //且记录为访问过了
                pre = node; 
            }else{
                //该节点入栈
                s.push(node); 
                //先访问右边
                root = node.right; 
            }
        }
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}

4. 求二叉树的层序遍历

4.1 题目描述

4.2 解题思路

方法一：非递归（推荐使用）

Java实现代码：

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer> > res = new ArrayList();
        if(root == null)
            //如果是空，则直接返回空数组
            return res; 
        //队列存储，进行层次遍历
        Queue<TreeNode> q = new ArrayDeque<TreeNode>(); 
        q.add(root);
        while(!q.isEmpty()){
            //记录二叉树的某一行
            ArrayList<Integer> row = new ArrayList();  
            int n = q.size();
            //因先进入的是根节点，故每层节点多少，队列大小就是多少
            for(int i = 0; i < n; i++){
                TreeNode cur = q.poll();
                row.add(cur.val);
                //若是左右孩子存在，则存入左右孩子作为下一个层次
                if(cur.left != null)
                    q.add(cur.left);
                if(cur.right != null)
                    q.add(cur.right);
            }
            //每一层加入输出
            res.add(row); 
        }
        return res;
    }
}

方法二：递归（扩展思路）

Java实现代码：

import java.util.*;
public class Solution {
    //记录输出
    ArrayList<ArrayList<Integer> > res = new ArrayList(); 
    void traverse(TreeNode root, int depth) {
        if(root != null){
            //新的一层
            if(res.size() < depth){  
                ArrayList<Integer> row = new ArrayList(); 
                res.add(row);
                row.add(root.val);
            //读取该层的一维数组，将元素加入末尾
            }else{ 
                ArrayList<Integer> row = res.get(depth - 1);
                row.add(root.val);
            }
        }
        else
            return;
        //递归左右时深度记得加1
        traverse(root.left, depth + 1); 
        traverse(root.right, depth + 1);
    }
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if(root == null)
            //如果是空，则直接返回
            return res; 
        //递归层次遍历 
        traverse(root, 1); 
        return res;
    }
}

5. 从前序与中序遍历序列构造二叉树（done）

5.1. 题目描述

5.2. 解题思路

方法一：递归

class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }

        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        
        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}

方法二：迭代

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}

6. 二叉树的层序遍历 II（done）

6.1. 题目描述

6.2. 解题思路

方法一：广度优先搜索

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            levelOrder.add(0, level);
        }
        return levelOrder;
    }
}


http://www.kler.cn/a/527335.html

相关文章：

  • “星门计划对AI未来的意义——以及谁将掌控它”
  • Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)(A,B,C,E1)
  • hot100（4）
  • 对比DeepSeek、ChatGPT和Kimi的学术写作关键词提取能力
  • Baklib推动企业知识管理创新与效率提升的全面探讨
  • 计算机网络 性能指标相关
  • Python——基本数据类型——字符串类型
  • 代码随想录刷题day20|（哈希表篇）15.三数之和
  • 机器学习6-全连接神经网络2
  • 基于改进的强跟踪技术的扩展Consider Kalman滤波算法在无人机导航系统中的应用研究
  • 使用 Ollama 和 Kibana 在本地为 RAG 测试 DeepSeek R1
  • LeetCode 0541.反转字符串 II：模拟
  • C# 数组和列表的基本知识及 LINQ 查询
  • Spring Boot 基础开发：实现 RESTful API 开发
  • 【算法设计与分析】实验4：动态规划—0/1背包问题
  • Baklib赋能企业实现高效数字化内容管理提升竞争力
  • 【基于SprintBoot+Mybatis+Mysql】电脑商城项目之用户注册
  • 第05章 16 Implicit Function应用举例
  • 【蓝桥杯】43697.机器人塔
  • origin如何在已经画好的图上修改数据且不改变原图像的画风和格式