代码随想录 Day18 - 二叉树(五)

简介: 代码随想录 Day18 - 二叉树(五)

作业题


513. 找树左下角的值

package jjn.carl.binary_tree;
import commons.BinaryTreeHelper;
import commons.TreeNode;
import java.util.ArrayList;
import java.util.List;
/**
 * @author Jiang Jining
 * @since 2023-07-16 10:10
 */
public class LeetCode513 {
    private int maxDepth = -1;
    private int bottomLeftValue;
    public int findBottomLeftValue(TreeNode root) {
        traversal(root, 0);
        return bottomLeftValue;
    }
    private void traversal(TreeNode node, int depth) {
        if (node.left == null && node.right == null) {
            if (depth > maxDepth) {
                maxDepth = depth;
                bottomLeftValue = node.val;
            }
            return;
        }
        if (node.left != null) {
            traversal(node.left, depth + 1);
        }
        if (node.right != null) {
            traversal(node.right, depth + 1);
        }
    }
    public static void main(String[] args) {
        List<Integer> input = new ArrayList<>(List.of(1));
        TreeNode node = BinaryTreeHelper.buildTree(input);
        int bottomLeftValue = new LeetCode513().findBottomLeftValue(node);
        System.out.println("bottomLeftValue = " + bottomLeftValue);
    }
}


112. 路径总和

/**
 * 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 {
    private boolean canReach;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum, 0);
        return canReach;
    }
    private void dfs(TreeNode node, int targetSum, int currentSum) {
        if(node == null) {
            return;
        }
        if(node.left == null && node.right == null) {
            if(currentSum + node.val == targetSum) {
                canReach = true;
            }
            return;
        }
        if(node.left != null) {
            dfs(node.left, targetSum, currentSum + node.val);
        }
        if(node.right != null) {
            dfs(node.right, targetSum, currentSum + node.val);
        }
    }
}


113. 路径总和 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>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, root, new ArrayList<>(), targetSum, 0);
        return result;
    }
    private void backtrack(List<List<Integer>> result, TreeNode root, List<Integer> path, int targetSum, int currentSum) {
        if(root == null) {
            return;
        }
        path.add(root.val);
        if(root.left == null && root.right == null) {
            if(currentSum + root.val == targetSum) {
                result.add(new ArrayList<>(path));   
            }
            return;
        }
        if(root.left != null) {
            backtrack(result, root.left, path, targetSum, currentSum + root.val);
             path.remove(path.size()- 1);
        }
        if(root.right != null) {
            backtrack(result, root.right, path, targetSum, currentSum + root.val);
             path.remove(path.size()- 1);
        }
    }
 }


106. 从中序与后序遍历序列构造二叉树

题目感觉有点复杂,后续二刷再研究吧。

记录一下规律:

前序 (中左右) 后序(左右中) 中序(左中右),必须有中序,加上前序或者后序,才能唯一确定一棵树,否则无法分割左右。

/**
 * 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 {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开,说明没有元素,返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数,用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);
        return root;
    }
}

目录
相关文章
|
Ubuntu 开发工具 git
Ubuntu 18.04 LTS简约美化(2020年定稿版)
目录 前言 gnome-tweak-tool 主题和图标等 最后 前言 之前我也写过一篇关于Ubuntu 16.04 LTS美化的. 其实大部分内容依旧实用, 不过由于Ubuntu的界面由unity变成了gnome, 所以有些小的变化.
4520 0
|
4天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
15天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1309 5
|
1天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。
|
14天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1345 87
|
1天前
|
JavaScript Java 大数据
基于JavaWeb的销售管理系统设计系统
本系统基于Java、MySQL、Spring Boot与Vue.js技术,构建高效、可扩展的销售管理平台,实现客户、订单、数据可视化等全流程自动化管理,提升企业运营效率与决策能力。
|
3天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
189 82
2025年阿里云域名备案流程(新手图文详细流程)