首页 > 编程语言 >代码随想录算法训练营第十五天 | 层序遍历 、226.翻转二叉树、101.对称二叉树

代码随想录算法训练营第十五天 | 层序遍历 、226.翻转二叉树、101.对称二叉树

时间：2024-05-24 15:28:00浏览次数：29  
标签：node deque right root 随想录 二叉树 null 第十五天 left

层序遍历

题目链接：
学会二叉树的层序遍历，可以一口气打完以下十题：

文档讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html
视频讲解：https://www.bilibili.com/video/BV1GY4y1u7b2

思路（层序遍历）

使用队列来辅助遍历。记录每一层的个数，然后弹出一个节点，就把他的左右孩子放进队列中。当这一层的个数为0，就开始遍历下一行。

代码

102.二叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        while (!deque.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int size = deque.size();
            while(size-- > 0) {
                TreeNode cur = deque.pollFirst();
                temp.add(cur.val);
                if (cur.left != null) deque.addLast(cur.left);
                if (cur.right != null) deque.addLast(cur.right);
            }
            res.add(temp);
        }
        return res;
    }
}

107.二叉树的层次遍历 II

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> temp = new ArrayList<>();
            while (size-- > 0) {
                TreeNode node = deque.pollFirst();
                temp.add(node.val);
                if (node.left != null) deque.addLast(node.left);
                if (node.right != null) deque.addLast(node.right);
            }
            res.add(temp);
        }
        Collections.reverse(res); // 翻转数组
        return res;
    }
}

199.二叉树的右视图

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.pollFirst();
                if (node.left != null) deque.addLast(node.left);
                if (node.right != null) deque.addLast(node.right);
                if (size == 0) res.add(node.val); // 遍历到本层最后一个节点再放入数组中
            }
        }

        return res;
    }
}

637.二叉树的层平均值

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            int size2 = deque.size();
            Double sum = 0D;
            while (size-- > 0) {
                TreeNode node = deque.pollFirst();
                sum += node.val;
                if (node.left != null) deque.addLast(node.left);
                if (node.right != null) deque.addLast(node.right);
            }
            res.add(sum / size2);
        }
        return res;
    }
}

429.N叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<Node> deque = new LinkedList<>();
        deque.addLast(root);
        while(!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> temp = new ArrayList<>();
            while (size-- > 0) {
                Node node = deque.pollFirst();
                temp.add(node.val);
                for (Node child : node.children) { // 这里放入孩子节点的list，而不是左孩子和右孩子
                    deque.addLast(child);
                }
            }
            res.add(temp);
        }
        return res;
    }
}

515.在每个树行中找最大值

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            int max = Integer.MIN_VALUE;
            while (size-- > 0) {
                TreeNode node = deque.pollFirst();
                max = Math.max(max, node.val);
                if (node.left != null) deque.addLast(node.left);
                if (node.right != null) deque.addLast(node.right);
            }
            res.add(max);
        }
        return res;
    }
}

116.填充每个节点的下一个右侧节点指针

class Solution {
    public Node connect(Node root) {
        if (root == null) return root;
        Deque<Node> deque = new LinkedList<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                Node node1 = deque.pollFirst();
                Node node2 = deque.peekFirst(); // 获得下一个节点的信息
                if (size == 0) node1.next = null;
                else node1.next = node2;
                if (node1.left != null) deque.addLast(node1.left);
                if (node1.right != null) deque.addLast(node1.right);
            }
        }
        return root;
    }
}

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

这道题目说是二叉树，上面的116题目说是完整二叉树，116的代码有判断左右孩子是否为空，所以这道题代码和116是一样的。

104.二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        int res = 0;
        if (root == null) return res;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.pollFirst();
                if (node.left != null) deque.addLast(node.left);
                if (node.right != null) deque.addLast(node.right);
            }
            res++;
        }
        return res;
    }
}

111.二叉树的最小深度

class Solution {
    public int minDepth(TreeNode root) {
        int depth = 0;
        if (root == null) return depth;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.pollFirst();
                if (node.left != null) deque.addLast(node.left);
                if (node.right != null) deque.addLast(node.right);
                if (node.left == null && node.right == null) return depth + 1; // 当左右孩子都为空，直接返回最小深度
            }
            depth++;
        }
        return depth;
    }
}

226.翻转二叉树

题目链接：https://leetcode.cn/problems/invert-binary-tree/
文档讲解：https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV1sP4y1f7q7

思路

  1. 确定递归函数的参数和返回值。
    参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。
    返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为TreeNode。
public TreeNode invertTree(TreeNode root)
  1. 确定终止条件。
    当前节点为空的时候，就返回。
if (root == null) return root;
  1. 确定单层递归的逻辑。
// 因为是前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。
swapChildren(root);
invertTree(root.left);
invertTree(root.right);

// 后序遍历就交换一下顺序。
swapChildren(root);
invertTree(root.left);
invertTree(root.right);

// 如果是中序遍历，是左-中-左，如果是左中右的话，翻转的右孩子就是之前翻转过来的左孩子。
invertTree(root.left);
swapChildren(root);
invertTree(root.left);

代码

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        swapChildren(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    public void swapChildren(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

101.对称二叉树

题目链接：https://leetcode.cn/problems/symmetric-tree/
文档讲解：https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV1ue4y1Y7Mf

思路

这道题只能用后序遍历，因为需要得到左右子树是否对称以后，返回给中间节点。

  1. 确定递归函数的参数和返回值。
    因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。返回值自然是boolean类型。
boolean compare(TreeNode left, TreeNode right)
  1. 确定终止条件。
    要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚，否则后面比较数值的时候就会操作空指针了。

节点为空的情况有：

  • 左节点为空，右节点不为空，不对称，return false
  • 左不为空，右为空，不对称 return false
  • 左右都为空，对称，返回true

此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：

  • 左右都不为空，比较节点数值，不相同就return false
  • 此时左右节点不为空，且数值也不相同的情况我们也处理了。
if (left == null && right == null) return true;
else if (left == null && right != null) return false;
else if (left != null && right == null) return false;
else if (left.val != right.val) return false;

注意上面最后一种情况，没有使用else，而是else if， 因为我们把以上情况都排除之后，剩下的就是左右节点都不为空，且数值相同的情况。

  1. 确定单层递归的逻辑
    此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
    比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
    比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
    如果左右都对称就返回true ，有一侧不对称就返回false 。
boolean outside = compare(left.left, right.right);
boolean inside = compare(left.right, right.left);
boolean res = outside && inside;
return res;

代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        else if (left == null && right != null) return false;
        else if (left != null && right == null) return false;
        else if (left.val != right.val) return false;
        boolean outside = compare(left.left, right.right);
        boolean inside = compare(left.right, right.left);
        boolean res = outside && inside;
        return res;
    }
}

标签：node,deque,right,root,随想录,二叉树,null,第十五天,left
From： https://blog.csdn.net/Danny_8/article/details/139150482

相关文章

  • 算法打卡 Day18（二叉树）-层序遍历 + 翻转二叉树 + 对称二叉树
    文章目录层序遍历相关题目Leetcode226-翻转二叉树题目描述解题思路Leetcode101-对称二叉树题目描述解题思路层序遍历我们使用队列模拟二叉树的层序遍历。相关题目102.二叉树的层序遍历classSolution{public:vector<vector<int>>levelOrder(TreeNode......
  • 算法打卡 Day14（二叉树）-理论基础 + 递归遍历 + 迭代遍历 + 统一迭代
    文章目录理论基础满二叉树完全二叉树二叉搜索树平衡二叉搜索树二叉树的存储方式链式存储顺序存储二叉树的遍历方式二叉树的定义递归遍历leetcode144-二叉树的前序遍历leetcode145-二叉树的后序遍历leetcode94-二叉树的中序遍历迭代遍历前序遍历后序遍历中序遍历统......
  • 代码随想录算法训练营第三十六天|860.柠檬水找零、406.根据身高重建队列、452. 用最少
    860.柠檬水找零文档讲解：代码随想录题目链接：.-力扣（LeetCode）注意看提示：bills[i] 不是 5 就是 10 或是 20 场景较为固定遇到了20，优先消耗10classSolution:deflemonadeChange(self,bills:List[int])->bool:total={5:0,10:0,20:0}......
  • 代码随想录算法训练营第二天|977(双指针)，209(滑动窗口)，59(螺旋矩阵)
    977.有序数组的平方**1.数组中有正有负，且本身有序。平方后，较大值从两边来比较取出。**2.使用头尾指针方法。209.长度最小的子数组**1.从数组中找符合要求的连续子数组**2.滑动窗口方法：本质为快慢双指针，快指针不断前进直到子数组满足要求，然后慢指针前进直到子数组不满足......
  • 基于双向堆栈的二叉树双向迭代算法
    前言之前一直在研究avl树的迭代算法。我参考了C++标准库map的实现，发现他们在树节点上使用了parent指针+一个状态标志位的形式，去实现动态迭代。但是我不想用parent指针，因为觉得会增加调整指针的时间还有浪费存储空间。于是，在我的不屑努力下，终于，找到了一种基于堆栈实现的双向迭代......
  • 代码随想录算法训练营第第15天 | 层序遍历10道题 、226.翻转二叉树 、101. 对称二叉树
    层序遍历看完本篇可以一口气刷十道题，试一试，层序遍历并不难，大家可以很快刷了十道题。题目链接/文章讲解/视频讲解：https://programmercarl.com/0102.二叉树的层序遍历.html层序遍历，10道题，一一通过，比较简单226.翻转二叉树（优先掌握递归）这道题目一些做过的同学理解的也不够深......
  • 代码随想录算法训练营第一天|704,34,35(二分查找),27(双指针)
    二分查找1.使用条件：数组，升序，值不唯一。2.时间复杂度O(logn)可分为左闭右闭，左闭右开两种区间类型来求解。左闭右闭:left=0,right=nums.Length-1,while(left<=right),right=middle-1.左闭右开:left=0,right=nums.Length,while(left<right),right=middle.......
  • 算法随想录打卡第一天|704. 二分查找、27. 移除元素
    704.二分查找-力扣（LeetCode）自己的解法是这样的，超出了时间限制，现在觉得应该是在mid的计算中出了问题。然后在mid的转换中没有right减去1或者left加上1。这两点的问题。自己很习惯的方式是左闭合加上右闭合。可以省去很多对于临界值忘记考虑的麻烦。超时代码贴出：publicin......
  • 代码随想录算法训练营第十四天 | 二叉树遍历
    递归法文章讲解视频讲解递归三要素：1确定递归函数的参数和返回值2确定终止条件3确定单层递归的逻辑前序遍历题目链接递归的参数和返回值：传入当前节点和保存结果集的数组，不需要返回值终止条件：当前节点为空时单层递归逻辑：保存当前节点的值到结果集中classSolution......
  • 代码随想录算法训练营第第14天 | 二叉树递归遍历（递归法、迭代、统一的迭代方法）
    递归遍历（必须掌握）二叉树的三种递归遍历掌握其规律后，其实很简单题目链接/文章讲解/视频讲解：https://programmercarl.com/二叉树的递归遍历.html迭代遍历（基础不好的录友，迭代法可以放过）题目链接/文章讲解/视频讲解：https://programmercarl.com/二叉树的迭代遍历.html统一迭代......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99