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

算法跟练第十一弹——二叉树

article 2025/2/19 8:10:21

文章目录

  • part01 递归遍历
    • 1.1 二叉树的前序遍历
    • 1.2 二叉树的中序遍历
    • 1.3 二叉树的后序遍历
  • part02 迭代遍历
    • 2.1 二叉树的前序遍历
    • 2.2 二叉树的中序遍历
    • 2.3 二叉树的后序遍历
  • part03 层序遍历
    • 3.1 二叉树的层序遍历
    • 3.2 二叉树的层序遍历II
    • 3.3 二叉树的右视图
  • 归纳
    • 获取双重链表的第一层

跟着代码随想录刷题的第十一天。

代码随想录链接：代码随想录

part01 递归遍历

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

1.1 二叉树的前序遍历

题目链接：二叉树的前序遍历

代码：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        pre(root,result);

        return result;
    }

    public void pre(TreeNode root,List<Integer>result){
        if(root==null){
            return;
        }

        result.add(root.val);
        pre(root.left,result);
        pre(root.right,result);

    }
}

1.2 二叉树的中序遍历

题目链接：二叉树的中序遍历

代码：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        pre(root,result);
        return result;
    }

    public void pre(TreeNode root,List<Integer>result){
        if(root == null)
            return;

        pre(root.left,result);
        result.add(root.val);
        pre(root.right,result);

    }
}

1.3 二叉树的后序遍历

题目链接：二叉树的后序遍历

代码：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        pre(root,result);
        return result;
    }

    public void pre(TreeNode root,List<Integer>result){
        if(root==null)
            return;

        pre(root.left,result);
        pre(root.right,result);
        result.add(root.val);
    }
}

part02 迭代遍历

2.1 二叉树的前序遍历

题目链接：二叉树的前序遍历

代码：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root==null)
            return result;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            result.add(stack.pop().val);
            if(node.right!=null)
                stack.push(node.right);
            if(node.left!=null)
                stack.push(node.left);
        }

        return result;
    }
}

2.2 二叉树的中序遍历

题目链接：二叉树的中序遍历

代码：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
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{
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        
        return result;
    }
}

题解：主要是要考虑应该将左孩子全部入栈，再出栈，出栈时判断是否存在右孩子，存在就把指针指向右孩子

2.3 二叉树的后序遍历

题目链接：二叉树的后序遍历

代码：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null)
            return result;

        stack.push(root);
        while(!stack.isEmpty())
        {
            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;
    }
}

题解：这次是利用链表的翻转，先中-右-左遍历，再翻转过来

part03 层序遍历

3.1 二叉树的层序遍历

题目链接：102.二叉树的层序遍历

代码：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root==null)
            return result;

        Queue<TreeNode> que = new LinkedList<>();
        int len = 0;
        que.add(root);
        while(!que.isEmpty()){
            len = que.size();
            List<Integer> q = new ArrayList<>();
            while(len>0){
                TreeNode cur = que.poll();
                if(cur.left!=null)que.add(cur.left);
                if(cur.right!=null)que.add(cur.right);
                q.add(cur.val);
                len--;
            }
            result.add(q);
        }

        return result;
    }
}

3.2 二叉树的层序遍历II

题目链接：102.二叉树的层序遍历II

代码：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root==null)
            return result;

        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        int len = 0;
        while(!que.isEmpty()){
            len = que.size();
            List<Integer> q = new ArrayList<>();
            while(len>0){
                TreeNode node = que.poll();
                if(node.left!=null)que.add(node.left);
                if(node.right!=null)que.add(node.right);
                q.add(node.val);
                len--;
            }
            result.add(q);
        }
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for(int i = result.size()-1;i>=0;i--){
            list.add(result.get(i));
        }

        return list;
    }
}

3.3 二叉树的右视图

题目链接：199.二叉树的右视图

代码：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root==null)
            return result;

        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        int len = 0;
        while(!que.isEmpty()){
            len = que.size();
            while(len>0){
                TreeNode node = que.poll();
                if(node.left!=null)que.add(node.left);
                if(node.right!=null)que.add(node.right);
                if(len==1)
                    result.add(node.val);
                len--;
            }
        }

        return result;
    }
}

归纳

获取双重链表的第一层

result.get(i)

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

相关文章：

  • debian和ubuntu安装python3.8并修改默认python版本
  • 小鹏自动驾驶 xnet 技术细节
  • 数​字​政​通​一​面
  • 我用AI做数据分析之四种堆叠聚合模型的比较
  • B端产品思考：使用AI帮助B端产品经理
  • 数智百问 | 制造企业如何降低产线检测数据的存储和管理成本？
  • Linux 配置 MySQL 定时自动备份到另一台服务器
  • Spring-Cloud-Nacos基础使用教程
  • [MySQL]2-MySQL索引
  • TCP 和 UDP 可以绑定相同的端口吗？
  • 批量修改mysql字符串字段子字符串
  • Win10环境借助DockerDesktop部署Open web UI集成DeepSeek
  • 9、Python面试题解析：函数的用法和高级
  • STM32 HAL库 CANbus通讯（C语言）
  • 基于SpringBoot+Vue的求职招聘管理系统
  • 自然语言处理NLP入门 -- 第一节基础概念
  • 【嵌入式Linux应用开发基础】open函数与close函数
  • oracle dbms_sqltune 使用
  • Visual Studio Code 的 AI 编程助手
  • 概率论、组合数学知识点汇总