每日一题 1372二叉树中的最长交错路径

这篇具有很好参考价值的文章主要介绍了每日一题 1372二叉树中的最长交错路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

给你一棵以 root 为根的二叉树,二叉树中的交错路径定义如下:

  • 选择二叉树中 任意 节点和一个方向(左或者右)。
  • 如果前进方向为右,那么移动到当前节点的的右子节点,否则移动到它的左子节点。
  • 改变前进方向:左变右或者右变左。
  • 重复第二步和第三步,直到你在树中无法继续移动。

交错路径的长度定义为:访问过的节点数目 - 1(单个节点的路径长度为 0 )。

请你返回给定树中最长 交错路径 的长度。

示例 1:

每日一题 1372二叉树中的最长交错路径,java,数据结构,算法,深度优先

输入:root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
输出:3
解释:蓝色节点为树中最长交错路径(右 -> 左 -> 右)。

示例 2:

每日一题 1372二叉树中的最长交错路径,java,数据结构,算法,深度优先

输入:root = [1,1,1,null,1,null,null,1,1,null,1]
输出:4
解释:蓝色节点为树中最长交错路径(左 -> 右 -> 左 -> 右)。

示例 3:文章来源地址https://www.toymoban.com/news/detail-691714.html

输入:root = [1]
输出:0

题解

/**
 * 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 int maxlen;
    public int longestZigZag(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root.left, 1, 1);
        dfs(root.right, 1, 2);
        return maxlen;
    }
    //定义一个int类型 1为左 2为右
    private void dfs(TreeNode root, int cnt, int direct) {
        if (root == null) {
            return;
        }
        maxlen = Math.max(maxlen,cnt);
        //如果没有调转方向 cnt归1
        dfs(root.left, direct == 1 ? 1 : cnt + 1, 1);
        dfs(root.right, direct == 2 ? 1 : cnt + 1, 2);
    }
}

到了这里,关于每日一题 1372二叉树中的最长交错路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每日一题 230二叉搜索树中第K小的元素(中序遍历)

    给定一个二叉搜索树的根节点  root  ,和一个整数  k  ,请你设计一个算法查找其中第  k   个最小元素(从 1 开始计数)。 示例 1: 示例 2:

    2024年02月10日
    浏览(41)
  • 算法---二叉树中的最大路径和

    二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ,返回其 最大路径和 。 示

    2024年02月11日
    浏览(36)
  • 【算法专题】二叉树中的深搜(DFS)

    深度优先遍历(DFS,全称为 Depth First Traversal),是我们树或者图这样的数据结构中常用的⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分支,直到一条路径上的所有节点都被遍历完毕,然后再回溯到上一层,继续找⼀条路遍历。 在二叉树中,常见的深度优先遍历为

    2024年02月03日
    浏览(40)
  • 每日一题——对称的二叉树

    题目 给定一棵二叉树,判断其是否是自身的镜像(即:是否对称) 例如: 下面这棵二叉树是对称的 下面这棵二叉树不对称。 数据范围:节点数满足 0≤n≤1000,节点上的值满足 ∣val∣≤1000 要求:空间复杂度 O(n),时间复杂度 O(n) 参数说明:二叉树类,二叉树序列化是通过

    2024年02月13日
    浏览(37)
  • 【每日一题】823. 带因子的二叉树

    给出一个含有不重复整数元素的数组 arr ,每个整数 arr[i] 均大于 1。 用这些整数来构建二叉树,每个整数可以使用任意次数。其中:每个非叶结点的值应等于它的两个子结点的值的乘积。 满足条件的二叉树一共有多少个?答案可能很大,返回 对 109 + 7 取余 的结果。 示例

    2024年02月11日
    浏览(30)
  • 力扣hot100 二叉树中的最大路径和 递归

    Problem: 124. 二叉树中的最大路径和 👨‍🏫 参考思路 时间复杂度: O ( n ) O(n) O ( n ) 空间复杂度: O ( n ) O(n) O ( n )

    2024年01月18日
    浏览(35)
  • 算法通关村——二分查找在二叉树中的应用

    二叉搜索树中的搜索 给定二叉搜索树(BST)的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。 一开始以为很难,无从下手,但是题目已经规定了这是二叉搜索树,意味着将元素按照中序排

    2024年02月13日
    浏览(36)
  • LeetCode算法递归类—二叉树中的最大路径和

    目录 124. 二叉树中的最大路径和 - 力扣(LeetCode) 题解: 代码: 运行结果: 二叉树中的  路径  被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中  至多出现一次  。该路径  至少包含一个  节点,且不一定经过根节点。 路径和

    2024年02月12日
    浏览(38)
  • 【数据结构】二叉树中的递归问题(超详细画图~)

    和光同尘_我的个人主页 不管风吹浪打,胜似闲庭信步。 --毛泽东 我本来还说上节难来着,没想到这节更难🥲 不过我既然会了保证xdm也能看懂👍 首先回顾下二叉树的概念 二叉树是由:空树 或者非空树(根节点,根节点的左子树、根节点的右子树)组成的 从概念中可以看出

    2024年02月07日
    浏览(35)
  • 每日一题 102二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例 1: 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] 示例 2: 输入:root = [1] 输出:[[1]] 示例 3: 输入:root = [] 输出:[] 提示: 树中节点数目在范围 [0, 2000] 内 -1000 =

    2024年02月09日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包