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;
    }
}