代码随想录 Day15 - 二叉树（二）
作者：jjn0703
- 2023-07-13 江苏
本文字数：1739 字
阅读完需：约 6 分钟
作业题
层序遍历，类似 BFS 写法，遍历每一层的时候，添加下一层的节点到队列中，避免死循环，需要在每一层开始遍历之前，就记录一下节点数量，并且将结果记录到数组。
102. 二叉树的层序遍历
package jjn.carl.binary_tree;
import commons.BinaryTreeHelper;import commons.TreeNode;
import java.util.*;
/** * @author Jiang Jining * @since 2023-07-12 23:40 */public class LeetCode102 { public List<List<Integer>> levelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode poll = queue.poll(); if (poll == null) { continue; } level.add(poll.val); if (poll.left != null) { queue.offer(poll.left); } if (poll.right != null) { queue.offer(poll.right); } } result.add(level); } return result; } public static void main(String[] args) { List<Integer> input = new ArrayList<>(); input.addAll(List.of(3, 9, 20)); input.add(null); input.add(null); input.add(15); input.add(7); TreeNode root = BinaryTreeHelper.buildTree(input); List<List<Integer>> levelledOrder = new LeetCode102().levelOrder(root); System.out.println("levelledOrder = " + levelledOrder); }}
复制代码
226. 翻转二叉树
/** * 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 invertTree(TreeNode root) { if (root == null) { return root; } TreeNode left = root.left; TreeNode right = root.right; root.left = invertTree(right); root.right = invertTree(left); return root; }}复制代码
101. 对称二叉树
借助函数 isSymmetricPairs 来判断两棵子树是否对称，即树 1 的左节点和树 2 的右节点，树 2 的左节点和树 1 的右节点是否相等。
/** * 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 isSymmetric(TreeNode root) { if (root == null) { return true; } return isSymmetricPairs(root.left, root.right); } private boolean isSymmetricPairs(TreeNode left, TreeNode right) { if (left == null && right == null) { return true; } if (left == null || right == null) { return false; } if (left.val != right.val) { return false; } return isSymmetricPairs(left.left, right.right) && isSymmetricPairs(left.right, right.left); }}复制代码
划线
评论
复制
发布于: 刚刚阅读数: 5
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/b2aa0c805da15145e9fc16b0e】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论