层序遍历
层序遍历
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入:root = []
输出:[]
提示:
- 树中节点数目在范围
[0, 2000]
内 -1000 <= Node.val <= 1000
/**
* 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>> levelOrder(TreeNode root) {
//采用队列形式,父节点进了之后让子节点进
Queue<TreeNode> treeNodes = new LinkedList<>();
List<List<Integer>> arrayLists = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
if (root!=null){
treeNodes.add(root);
}
while (!treeNodes.isEmpty()){
//只能每一次获取队列的大小,不然会wA
int n = treeNodes.size();
for (int i = 0; i < n; i++) {
TreeNode poll = treeNodes.poll();
if (poll.left!=null){
treeNodes.add(poll.left);
}
if (poll.right!=null){
treeNodes.add(poll.right);
}
list.add(poll.val);
}
arrayLists.add(list);
list = new ArrayList<>();
}
return arrayLists;
}
}
//leetcode submit region end(Prohibit modification and deletion)
层序遍历 Ⅱ
给你二叉树的根节点 root
,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[15,7],[9,20],[3]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入:root = []
输出:[]
提示:
- 树中节点数目在范围
[0, 2000]
内 -1000 <= Node.val <= 1000
与上题不同的就只是插入大列表的时候是从头插
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
LinkedList<TreeNode> treeNodes = new LinkedList<>();
List<List<Integer>> lists = new ArrayList<>();
ArrayList<Integer> integers = new ArrayList<>();
if (root!=null){
treeNodes.add(root);
}
while(!treeNodes.isEmpty()){
int n = treeNodes.size();
for (int i = 0;i<n;i++){
TreeNode poll = treeNodes.poll();
integers.add(poll.val);
if (poll.left!=null){
treeNodes.add(poll.left);
}
if(poll.right!=null){
treeNodes.add(poll.right);
}
}
lists.add(0,integers);
integers = new ArrayList<Integer>();
}
return lists;
}
}
给定一个二叉树 root
,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:3
示例 2:
输入:root = [1,null,2]
输出:2
提示:
- 树中节点的数量在
[0, 104]
区间内。 -100 <= Node.val <= 100
class Solution {
public int maxDepth(TreeNode root) {
Queue<TreeNode> treeNodes = new LinkedList<TreeNode>();
int i = 0;
if (root!=null){
treeNodes.add(root);
}
while(!treeNodes.isEmpty()){
int n = treeNodes.size();
for (int j = 0; j < n; j++) {
TreeNode poll = treeNodes.poll();
if (poll.left!=null){
treeNodes.add(poll.left);
}
if (poll.right!=null){
treeNodes.add(poll.right);
}
}
i++;
}
return i;
}
}
给你二叉树的根节点 root
,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[20,9],[15,7]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入:root = []
输出:[]
提示:
- 树中节点数目在范围
[0, 2000]
内 -100 <= Node.val <= 100
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> arrayLists = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
boolean q = false;
if (root!=null){
queue.add(root);
}
while(!queue.isEmpty()){
int n = queue.size();
for (int i = 0; i < n; i++) {
TreeNode poll = queue.poll();
list.add(poll.val);
if (poll.left!=null){
queue.add(poll.left);
}
if(poll.right!=null){
queue.add(poll.right);
}
}
if (q){
Collections.reverse(list);
}
arrayLists.add(list);
list = new ArrayList<Integer>();
q=!q;
}
return arrayLists;
}
}
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
提示:
- 树中节点数的范围在
[0, 105]
内 -1000 <= Node.val <= 1000
- 考虑左右都没子节点
class Solution {
public int minDepth(TreeNode root) {
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
int deep = 0;
if (root!=null){
queue.add(root);
}else{
return deep;
}
while(!queue.isEmpty()){
int n = queue.size();
for (int i = 0; i < n; i++) {
TreeNode poll = queue.poll();
if (poll.left!=null){
queue.add(poll.left);
}
if (poll.right!=null){
queue.add(poll.right);
}
if (poll.left==null&&poll.right==null){
return ++deep;
}
}
deep++;
}
return deep;
}
}
给你二叉树的根节点 root
和一个表示目标和的整数 targetSum
。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum
。如果存在,返回 true
;否则,返回 false
。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。
示例 2:
输入:root = [1,2,3], targetSum = 5
输出:false
解释:树中存在两条根节点到叶子节点的路径:
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3:
输入:root = [], targetSum = 0
输出:false
解释:由于树是空的,所以不存在根节点到叶子节点的路径。
提示:
- 树中节点的数目在范围
[0, 5000]
内 -1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
LinkedList<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> integers = new ArrayList<>();
if(root!=null){
queue.add(root);
TreeNode poll = queue.poll();
if (poll.left!=null){
poll.left.val += poll.val;
queue.add(poll.left);
}
if (poll.right!=null){
poll.right.val +=poll.val;
queue.add(poll.right);
}
if (poll.left==null&&poll.right==null){
integers.add(poll.val);
}
}
while(!queue.isEmpty()){
int n = queue.size();
for (int i = 0; i < n; i++) {
TreeNode poll = queue.poll();
if (poll.left!=null){
poll.left.val += poll.val;
queue.add(poll.left);
}
if (poll.right!=null){
poll.right.val +=poll.val;
queue.add(poll.right);
}
if (poll.left==null&&poll.right==null){
integers.add(poll.val);
}
}
}
int i = integers.indexOf(targetSum);
if (i!=-1){
return true;
}else{
return false;
}
}
}
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL
。
初始状态下,所有 next 指针都被设置为 NULL
。
示例 1:
输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,'#' 标志着每一层的结束。
示例 2:
输入:root = []
输出:[]
提示:
- 树中节点的数量在
[0, 212 - 1]
范围内 -1000 <= node.val <= 1000
class Solution {
public Node connect(Node root) {
LinkedList<Node> nodes = new LinkedList<Node>();
ArrayList<Node> list = new ArrayList<Node>();
if(root!=null){
nodes.add(root);
}
while(!nodes.isEmpty()){
int n = nodes.size();
for (int i = 0; i < n; i++) {
Node poll = nodes.poll();
list.add(poll);
if (poll.left!=null){
nodes.add(poll.left);
}
if (poll.right!=null){
nodes.add(poll.right);
}
}
for (int i = 0; i < list.size()-1; i++) {
list.get(i).next = list.get(i+1);
}
list.get(list.size()-1).next=null;
list.clear();
}
return root;
}
}
评论 (0)