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
但如果不需遍历所有结点,而是中途下车,那么使用队列会有效果文章来源地址https://www.toymoban.com/news/detail-827209.html
到了这里,关于随想录刷题笔记 —二叉树篇3 117填充每个节点的下一个右侧节点指针II 104二叉树最大深度 111二叉树最小深度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!