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

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/class Solution {public Node connect(Node root) {Deque<Node> que=new ArrayDeque<>();if(root==null){return null;}que.offer(root);while(!que.isEmpty()){int size=que.size();Node preNode=null;Node node=null;for (int i = 0; i < size; i++) {if(i==0){//取出本层头部结点preNode=que.poll();node=preNode;}else{node=que.poll();preNode.next=node;preNode=node;}if(node.left!=null){que.offer(node.left);}if(node.right!=null){que.offer(node.right);}}preNode.next=null; //本层最后一个节点指向null}return root;}
}

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

给定一个二叉树：

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/class Solution {public Node connect(Node root) {Deque<Node> que=new ArrayDeque<>();if(root==null){return null;}que.offer(root);while(!que.isEmpty()){int size=que.size();Node preNode=null;Node node=null;for (int i = 0; i < size; i++) {if(i==0){//取出本层头部结点preNode=que.poll();node=preNode;}else{node=que.poll();preNode.next=node;preNode=node;}if(node.left!=null){que.offer(node.left);}if(node.right!=null){que.offer(node.right);}}preNode.next=null; //本层最后一个节点指向null}return root;}
}

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

import java.util.ArrayDeque;
import java.util.Deque;/*** @author light* @Description 二叉树的最大深度** 给定一个二叉树 root ，返回其最大深度。* 二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。* @create 2023-08-16 16:46*/
public class MaxDepthTest {public static void main(String[] args) {Integer[] arr={3,9,20,null,null,15,7};BinaryTree2 tree2=new BinaryTree2(arr); //按数组方式创建二叉树System.out.println(maxDepth(tree2.root));}public static int maxDepth(TreeNode root) {Deque<TreeNode> que=new ArrayDeque<>();if(root!=null){que.offer(root);}int depth=0;while(!que.isEmpty()){int size=que.size();while(size>0){TreeNode node=que.poll();if(node.left!=null){que.offer(node.left);}if(node.right!=null){que.offer(node.right);}size--;if(size==0){depth++;}}}return depth;}
}

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

import java.util.ArrayDeque;
import java.util.Deque;/*** @author light* @Description 二叉树的最小深度** 给定一个二叉树，找出其最小深度。* 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。* 说明：叶子节点是指没有子节点的节点。* @create 2023-08-16 16:58*/
public class MinDepthTest {public static void main(String[] args) {Integer[] arr={3,9,20,null,null,15,7};BinaryTree2 tree2=new BinaryTree2(arr); //按数组方式创建二叉树System.out.println(minDepth(tree2.root));}public static int minDepth(TreeNode root) {Deque<TreeNode> que=new ArrayDeque<>();int depth=0;if(root!=null){que.offer(root);depth++;}while(!que.isEmpty()){int size=que.size();while(size>0){TreeNode node=que.poll();if(node.left==null&&node.right==null){return depth;}if(node.left!=null){que.offer(node.left);}if(node.right!=null){que.offer(node.right);}size--;if(size==0){depth++;}}}return depth;}
}

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

/*** 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) {Deque<TreeNode> que=new ArrayDeque<>();if(root!=null){que.offer(root);}while(!que.isEmpty()){int size=que.size();while(size>0){TreeNode node=que.poll();swap(node);if(node.left!=null){que.offer(node.left);}if(node.right!=null){que.offer(node.right);}size--;}}return root;}private  void swap(TreeNode root) {TreeNode temp=root.left;root.left=root.right;root.right=temp;}}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/94002.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！