leetcode之广度优先搜索

993. 二叉树的堂兄弟节点

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。 如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。 我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。

示例 1： 输入：root = [1,2,3,4], x = 4, y = 3 输出：false

示例 2： 输入：root = [1,2,3,null,4,null,5], x = 5, y = 4 输出：true 示例 3： 输入：root = [1,2,3,null,4], x = 2, y = 3 输出：false

/** * 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 isCousins(TreeNode root, int x, int y) { if(root==null||x==root.val||y==root.val) return false; Queue<TreeNode> que=new LinkedList<>(); TreeNode xnode=null,ynode=null,xfather=null,yfather=null; que.offer(root); while(!que.isEmpty()){ int size=que.size(); while(size-->0){ TreeNode temp= que.poll(); if(temp.left!=null){ que.offer(temp.left); if(temp.left.val==x){ xnode=temp.left; xfather=temp; } if(temp.left.val==y){ ynode=temp.left; yfather=temp; } } if(temp.right!=null){ que.offer(temp.right); if(temp.right.val==x){ xnode=temp.right; xfather=temp; } if(temp.right.val==y){ ynode=temp.right; yfather=temp; } } if(xnode!=null&&ynode!=null){ return xfather!=yfather; }else if(xnode==null&&ynode==null){ }else if(size==0){ return false; } } } return false; } }

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。

示例: 给定二叉树 [3,9,20,null,null,15,7], 返回它的最小深度 2.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int minDepth(TreeNode root) { if(root==null) return 0; if(root.left==null&&root.right==null) return 1; Queue<TreeNode> que=new LinkedList<>(); int count=1; que.offer(root); while(!que.isEmpty()){ int len=que.size(); while(len-->0){ TreeNode temp=que.poll(); if(temp.left==null&&temp.right==null) return count; if(temp.left!=null){ que.offer(temp.left); } if(temp.right!=null){ que.offer(temp.right); } } count++; } return count; } }

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 但是这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

思路：递归实现

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { return balance(root,root); } boolean balance(TreeNode p,TreeNode q){ if(p==null&&q==null) return true; if(p==null||q==null) return false; return p.val==q.val&&balance(p.left,q.right)&&balance(p.right,q.left); } }

思路：非递归实现

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { return balance(root,root); } boolean balance(TreeNode p,TreeNode q){ Queue<TreeNode> que=new LinkedList<>(); que.offer(p); que.offer(q); while(!que.isEmpty()){ TreeNode u=que.poll(); TreeNode v=que.poll(); if(u==null&&v==null) continue; if(u==null||v==null||u.val!=v.val) return false; que.offer(u.left); que.offer(v.right); que.offer(u.right); que.offer(v.left); } return true; } }

剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如: 给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果： [ [3], [9,20], [15,7] ]

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> lists=new ArrayList<>(); Queue<TreeNode> que=new LinkedList<>(); if(root==null) return lists; que.offer(root); while(!que.isEmpty()){ int len=que.size(); List<Integer> list=new ArrayList<>(); while(len-->0){ TreeNode temp=que.poll(); list.add(temp.val); if(temp.left!=null){ que.offer(temp.left); } if(temp.right!=null){ que.offer(temp.right); } } lists.add(list); } return lists; } }