随想录刷题笔记 —二叉树篇3 117填充每个节点的下一个右侧节点指针II 104二叉树最大深度 111二叉树最小深度

这篇具有很好参考价值的文章主要介绍了随想录刷题笔记 —二叉树篇3 117填充每个节点的下一个右侧节点指针II 104二叉树最大深度 111二叉树最小深度。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

117填充每个节点的下一个右侧节点指针II

和116的区别在于116是完美二叉树,而117中的结点并非左右子结点都存在。

解法一:队列

class Solution {
    public Node connect(Node root) {
        if (root == null){
            return root;
        }
        Queue<Node> nodes = new LinkedList<>();
        nodes.offer(root);
        int count = 1;
        Node node1 = null;
        Node node2 = null;
        while (!nodes.isEmpty()){
            node2 = nodes.poll();
            count--;
            if (node2.left!=null){
                nodes.offer(node2.left);
            }
            if (node2.right!=null){
                nodes.offer(node2.right);
            }
            if (node1==null){
                node1 = node2;
            }else {
                node1.next = node2;
            }
            if (count==0){
                node2.next = null;
                node1 = null;
                count = nodes.size();
            }else {
                node1 = node2;
            }
        }
        return root;
    }
}

解法二:双循环代替队列

class Solution {
    public Node connect(Node root) {
        Node dummy = new Node();
        Node cur = root;
        while (cur != null) {
            dummy.next = null;
            Node nxt = dummy; // 下一层的链表
            while (cur != null) { // 遍历当前层的链表
                if (cur.left != null) {
                    nxt.next = cur.left; // 下一层的相邻节点连起来
                    nxt = nxt.next;
                }
                if (cur.right != null) {
                    nxt.next = cur.right; // 下一层的相邻节点连起来
                    nxt = nxt.next;
                }
                cur = cur.next; // 当前层链表的下一个节点
            }
            cur = dummy.next; // 下一层链表的头节点
        }
        return root;
    }
}

104二叉树的最大深度

解法一:队列

使用depth标记深度,进行层序遍历,每遍历完一层,depth+1

class Solution {
    public int maxDepth(TreeNode root) {
        if (root==null){
            return 0;
        }
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.offer(root);
        int count = 1;
        int depth = 0;
        while (!nodes.isEmpty()){
            TreeNode temp = nodes.poll();
            count--;
            if (temp.right!=null){
                nodes.offer(temp.right);
            }
            if (temp.left!=null){
                nodes.offer(temp.left);
            }
            if (count==0){
                depth++;
                count = nodes.size();
            }
        }
        return depth;
    }
}

解法二:递归

递归出口:传入结点为空,返回0

否则返回左子结点和右子结点返回值的最大值

class Solution {
    public int maxDepth(TreeNode root) {
        if (root==null){
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }
}

111二叉树最小深度

解法一:队列,需要在左右子结点都是空时break,跳出循环

class Solution {
    public int minDepth(TreeNode root) {
        if (root==null){
            return 0;
        }
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.offer(root);
        int count = 1;
        int depth = 1;
        while (!nodes.isEmpty()){
            TreeNode temp = nodes.poll();
            count--;
            if (temp.right!=null){
                nodes.offer(temp.right);
            }
            if (temp.left!=null){
                nodes.offer(temp.left);
            }
            if (temp.right==null&&temp.left==null){
                break;
            }
            if (count==0){
                depth++;
                count = nodes.size();
            }
        }
        return depth;
    }
}

解法二:递归

递归效果并不好,递归会遍历所有结点,无法向队列一样中途检测退出。

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null)
            return 0;
        
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if(left == 0 && right == 0){
            return 1;
        } else if(left == 0){
            return right + 1;
        } else if(right == 0){
            return left + 1;
        }
        return Math.min(left, right) + 1;
    }
}

收获

如果需要遍历所有结点时,使用递归会有较好效果

但如果不需遍历所有结点,而是中途下车,那么使用队列会有效果文章来源地址https://www.toymoban.com/news/detail-827209.html

到了这里,关于随想录刷题笔记 —二叉树篇3 117填充每个节点的下一个右侧节点指针II 104二叉树最大深度 111二叉树最小深度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 代码随想录 二叉树 Java(二)

    采用前序遍历的方式遍历该二叉树,然后统计该二叉树的节点个数 这种方式比较简单,但是没有利用题目中所给的完全二叉树这一信息 官方思路:二分查找+位运算 对于任意二叉树,都可以通过广度优先搜索或深度优先搜索计算节点个数,时间复杂度和空间复杂度都是O(n),

    2024年02月08日
    浏览(50)
  • 代码随想录day13 | 226.翻转二叉树 101.对称二叉树

    使用前、后序反转最为方便。 为啥不推荐中序? 中序遍历,某些节点的左右孩子会翻转两次,某些节点左右孩子不会被反转。 101.对称二叉树 关键在于,看这个节点对应的左子树和右子树是否可以相互反转。 1、如何比较呢? 比较的是两个子树的里侧和外侧的元素是否相等

    2024年02月15日
    浏览(39)
  • 第18天-代码随想录刷题训练-第六章● 513.找树左下角的值 ● 112. 路径总和 113.路径总和ii ● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

    - LeetCode链接 给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 遍历顺序,因为本题要求的是 最后一层最左边的节点,因此只要遍历顺序 左节点在右节点前就行,因此 任何遍历顺序都可以 本题中的中节点 不需要处

    2024年02月04日
    浏览(51)
  • 1月3日代码随想录反转二叉树

    给你一棵二叉树的根节点  root  ,翻转这棵二叉树,并返回其根节点。 示例 1: 示例 2: 示例 3: 提示: 树中节点数目范围在  [0, 100]  内 -100 = Node.val = 100 这道题用递归的思想就是将根节点的左右儿子交换,然后再对子节点进行递归操作,直到子节点均为空。 但是我感觉

    2024年02月03日
    浏览(46)
  • 代码随想录day21(2)二叉树:二叉树的所有路径(leetcode257)

    题目要求:按任意顺序返回所有从根节点到叶节点的路径 思路:我们先递归地进行前序遍历,同时要注意回溯的过程,注意一些库的用法即可。 leetcode实战: 代码实现:

    2024年03月18日
    浏览(49)
  • 【Day22-慢就是快】代码随想录-二叉树-迭代遍历

    用迭代法实现二叉树的前后中序遍历。 递归的实现就是:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中 ,然后递归返回的时候,从栈顶弹出上一次递归的各项参数,所以这就是递归为什么可以返回上一层位置的原因。 此时大家应该知道我们用栈

    2024年02月10日
    浏览(46)
  • 【代码随想录day21】二叉树的最近公共祖先

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 这题的难点在于: 如何建

    2024年02月15日
    浏览(44)
  • 代码随想录额外题目| 二叉树 ●129求根到叶数字之和 ●1382二叉树变平衡●100相同的树

    #129求根到叶数字之和 回溯放进vector,然后从后往前拿,乘1 10 100 ... 很基础的回溯 my code: 随想录跟我思路差不多,但这两个是放globa的:int result; vectorint path; 最近总觉得global不安全不想放  #1382二叉树变平衡 本来遇到这种会换root的就头疼,然后看了眼随想录,是要先变成

    2024年02月14日
    浏览(33)
  • 代码随想录刷题笔记3

    本质上:穷举 + 剪枝。 回溯法就是解决这种k层for循环嵌套的问题。 for循环横向遍历,递归纵向遍历,回溯不断调整结果集。 注意画出 解空间树-N叉树。 组合无序,排列有序。 N叉树的宽度——横向遍历,N叉树的高度——纵向遍历。 而ans.push,path 是一个 std::vector 对象,当

    2024年02月02日
    浏览(52)
  • 【代码随想录】刷题笔记Day43

    刚过完非常愉快的元旦假期,唔想反工啊啊啊,先刷刷题找回学习的状态吧 dp[target] == target为目标,weight和value相同的01背包问题,用一维遍历 dp[j]为容量为j的背包所能装的最大价值 dp[j] = max(dp[j], dp[j - num[i]] + nums[i]) 关键在于把两两相减问题转化为两堆近似相减,和上一题就

    2024年02月03日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包