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

Java算法 二叉树入门 力扣简单题相同的树 翻转二叉树 判断对称二叉树 递归求二叉树的层数

article 2025/1/18 14:51:22

目录

模版

先序遍历

中序遍历

后序遍历

力扣原题 相同的二叉树

力扣原题 翻转二叉树

遍历树的层数

题目

静态变量

核心逻辑

模版

    // 二叉树
    public static class Node{
    	public int value;
    	public Node left;
    	public Node right;
    	public Node(int v) {
    		value=v;
    	}
    }

先序遍历

根节点 左孩子节点 右孩子节点

中序遍历

左孩子节点 根节点 右孩子节点

后序遍历

左孩子节点 右孩子节点 根节点

力扣原题 相同的二叉树

100. 相同的树 - 力扣（LeetCode）

/**
 * 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 boolean isSameTree(TreeNode p, TreeNode q) {
        
        if(p==null && q!=null){
            return false;
        }

        if(p!=null && q==null){
            return false;
        }

        if(p==null && q==null){
            return true;
        }
        // 都不为空
        return p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

力扣原题 翻转二叉树

/**
 * 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 TreeNode flipTree(TreeNode root) {
        if(root == null) return null;
        TreeNode tmp = root.left;
        root.left = flipTree(root.right);
        root.right = flipTree(tmp);
        return root;
    }
}

遍历树的层数

题目

静态变量

核心逻辑

import java.util.*;
import java.math.*;
import java.time.*;
import java.io.*;
import java.util.regex.*;
 
// Eclipse IDE 2020 08
// OpenJDK 1.8
// 下方网页是个人主页
// http://gczdy.cn
 
/*
                                   .-'''-.     
_______     _______               '   _    \   
\  ___ `'.  \  ___ `'.          /   /` '.   \  
 ' |--.\  \  ' |--.\  \        .   |     \  '  
 | |    \  ' | |    \  '       |   '      |  ' 
 | |     |  '| |     |  '      \    \     / /  
 | |     |  || |     |  | _    _`.   ` ..' /   
 | |     ' .'| |     ' .'| '  / |  '-...-'`    
 | |___.' /' | |___.' /'.' | .' |              
/_______.'/ /_______.'/ /  | /  |              
\_______|/  \_______|/ |   `'.  |              
                       '   .'|  '/             
                        `-'  `--'              
*/
 
/**
 * 
 * @Author Dduo
 * @Date 2025-01-10
 */
public class Main {
	
//    普通流
//    static Scanner sc = new Scanner(System.in);
    
//    数据流快读模板(类似于C++的IOS)
    static Read sc=new Read();
    
//    时间类 用来测试运行时间
    static Instant START=Instant.now();
    
    static long MOD = (long) (1e9 + 7);
    static int[] dx = {0, 0, 1, -1, 1, -1, 1, -1};
    static int[] dy = {1, -1, 0, 0, -1, -1, 1, 1};
    private static final int[] DIRECTIONS = {-1, 0, 1, 0, -1};
    
    /**
     *
     * @param args
     * @return
     * @throws Exception 
     */
    public static void main(String[] args) throws Exception {
 
        int t = 1;
//        t = sc.nextInt();
        
//      预处理
        preconditioning();
        
        while (t-- > 0) {
            solve();
        }
        
//   	 	sc.close();
//			dduoln("运行时间 : "+Duration.between(START,Instant.now()).toMillis()+"ms");
        return;
    }
    
//    输出流  
    static <T> void dduoln(T t) {
    	System.out.println(t);
    }
    
    static <T> void dduo(T t) {
    	System.out.print(t);
    }
    
    
//  预处理
    static void preconditioning() {
	
    }
    
//    数据结构模板 二叉树 by Dduo
    static class Node{
    	public int value;
    	public Node left;
    	public Node right;
     	public Node() {}
    	public Node(int v) {
    		value=v;
    	}
    }
    
//    静态变量
    static Node[] a = new Node[1000010];
    static int cnt=0;
    
//    核心代码逻辑
    static void solve() throws Exception { 	
    	// 构造二叉树
    	int n=sc.nextInt();
    	for(int i=1;i<=n;i++) {
    		a[i]=new Node(i);
    		int l=sc.nextInt();
    		int r=sc.nextInt();
            if (l != 0) {
                a[i].left = new Node(l);
            }
            if (r != 0) {
                a[i].right = new Node(r);
            }
    	}
    	dfs(a[1],1);
    	dduoln(cnt);
    }
    
    static void dfs(Node node,int max){
//    	   System.out.println("Visiting Node " + node.value + " at depth " + max);
    	 // 判断当前节点是否是叶子节点（即左右子节点都为null）
        if (node.left == null && node.right == null) {
            cnt = Math.max(cnt, max);
            return; 
        }
        // 遍历左子树
        if (node.left != null) {
            dfs(a[node.left.value], max + 1);
        }
        // 遍历右子树
        if (node.right != null) {
            dfs(a[node.right.value], max + 1);
        }
    }
    
    
    // 快速幂模版 by Dduo
    static long pow(long a, long b) {
        if (b == 0) return 1;
        if (b == 1) return a;
         
        try {
            long result = 1;
            while (b > 0) {
                if ((b & 1) == 1) {
                    if (result > Long.MAX_VALUE / a) return Long.MAX_VALUE;
                    result *= a;
                }
                b >>= 1;
                if (b > 0) {
                    if (a > Long.MAX_VALUE / a) return Long.MAX_VALUE;
                    a *= a;
                }
            }
            return result;
        } catch (Exception e) {
            return Long.MAX_VALUE;
        }
    }
}
 
// 数据结构模版 并查集 by Dduo
class UnionFind {
    private int[] parent;
    private int[] size;
    // 初始化并查集
    public UnionFind(int n) {
        parent = new int[n + 1]; // 因为编号从 1 到 N，所以数组大小是 N+1
        size = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i; // 每个元素的父节点初始为自己
            size[i] = 1;   // 每个元素的初始大小为 1
        }
    }
    // 查找元素 x 所在的集合，带路径压缩优化
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }
    // 合并两个集合 带按秩合并优化
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
 
        if (rootX != rootY) {
            // 按秩合并 较小的树合并到较大的树上
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
        }
    }
 
    // 判断 x 和 y 是否在同一个集合中
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}
 
// 数据流快读模板(类似于C++的IOS) by Dduo
class Read{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public Read(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
//    以下为输入部分:
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        //确定下一个token只有一个字符的时候再用
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public byte nextByte() throws IOException{
        return Byte.parseByte(next());
    }
    public short nextShort() throws IOException{
        return Short.parseShort(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
//    以下为输出部分:
    public void println(int a) throws IOException{
        print(a);
        println();
        return;
    }
    public void print(int a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(String a) throws IOException{
        print(a);
        println();
        return;
    }
    public void print(String a) throws IOException{
        bw.write(a);
        return;
    }
    public void println(long a) throws IOException{
        print(a);
        println();
        return;
    }
    public void print(long a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(double a) throws IOException{
        print(a);
        println();
        return;
    }
    public void print(double a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void print(BigInteger a) throws IOException{
        bw.write(a.toString());
        return;
    }
    public void print(char a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(char a) throws IOException{
        print(a);
        println();
        return;
    }
    public void println() throws IOException{
        bw.newLine();
        return;
    }
//    其他调试命令：
    public void flush() throws IOException{
//      交互题分组调试，或者提前退出的情况下可以先运行此语句再推出
        bw.flush();
        return;
    }
    public boolean hasNext() throws IOException{
//      本地普通IDE难以使用这个方法调试，需要按照数据组flush，刷新语句:
//      sc.flush()
//      调试完可删去
        return bf.ready();
    }
}

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

相关文章：

  • 【Rust自学】13.2. 闭包 Pt.2：闭包的类型推断和标注
  • 在Mac mini上实现本地话部署AI和知识库
  • Java中的依赖注入是什么？它如何工作？
  • 读取长文本，使用读取底表
  • 一文掌握Docker
  • 一次完整的tcpdump -XX输出报文详解
  • 刷题记录 回溯算法-16：47. 全排列 II
  • 从玩具到工业控制--51单片机的跨界传奇【3】
  • NLP入门书籍《掌握NLP：从基础到大语言模型》免费下载pdf
  • MySQL的日期时间类型
  • 《汽车维修技师》是什么级别的期刊？是正规期刊吗？能评职称吗？
  • Vue.js组件开发-实现后端返回二进制文件在浏览器自动下载
  • 基于R语言的现代贝叶斯统计学方法（贝叶斯参数估计、贝叶斯回归、贝叶斯计算实践过程
  • 如何通俗易懂的理解 html js css
  • idea 如何安装 github copilot
  • WPF实现动态四宫格布局
  • 灰度发布、金丝雀部署与蓝绿部署：软件发布的三把利剑
  • Redis | 第6章 事件与客户端《Redis设计与实现》
  • Ubuntu 部署Docker + Dify,遇到的坑, 最新亲测镜像
  • 如何在亚马逊云科技上大幅降低无服务器网页应用冷启动时间（上篇）
  • 在Mac m2系统下安装InSAR软件isce2
  • Python根据图片生成学生excel成绩表
  • [创业之路-254]：《华为数字化转型之道》-1-华为是一个由客户需求牵引、高度数字化、高度智能化、由无数个闭环流程组成的价值创造、评估、分配系统。
  • 学习微信小程序的下拉列表控件-picker
  • NC65增加按钮打开其他单据
  • DX12 快速教程(3) —— 画矩形