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

给定的二叉树 不是 完美二叉树 ，每一个节点并非都有两个子结点

左右节点可能缺失

一般思路：按照广度搜索处理，也可理解为按照树的层次来处理

从上往下，将树由一层一层处理下来

从首结点存入队列开始，一直从队列中取完所有的节点

取出节点处理其左右子结点的next，按照该节点的next去寻找左右子结点的next，再将子结点入队

class Solution {
    public Node connect(Node root) {
        if(root == null) {
            return root;
        }
        //按队列将树一层层的处理下来，可以保证使用节点next寻找时，可以遍历到真正的结尾
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        Node ans = root;
        while(!queue.isEmpty()) {
            root = queue.poll();
            if(root.left != null) {//左子结点不空
                if(root.right == null) {
                    Node t = root.next;
                    while(t != null) {//一直在自己的next中寻找他们的左右子结点是否可以作为自己左子结点的next
                        if(t.left != null) {
                            root.left.next = t.left;
                            t = null;
                        } else if(t.right != null) {
                            root.left.next = t.right;
                            t = null;
                        } else {
                            t = t.next;
                        }
                    }
                } else {//右子结点不空，则可作为左子结点的next
                    root.left.next = root.right;
                }
                queue.offer(root.left);//不空则入队
            }
            if(root.right != null) {//右子结点不空
                Node t = root.next;
                while(t != null) {
                    if(t.left != null) {
                        root.right.next = t.left;
                        t = null;
                    } else if(t.right != null) {
                        root.right.next = t.right;
                        t = null;
                    } else {
                        t = t.next;
                    }
                }
                queue.offer(root.right);//入队
            }
        }
        return ans;
    }
}

二、另一棵树的子树

给定一颗树，再给定一个可能的子树

当子树出现在大树上：子树的每个节点都在大树上，且结构与子树保持一致

利用广度优先搜索，查找可能的子树根节点，直到确认子树存在或者搜索完全部节点

出现子树根节点后，利用深度优先搜索去判断大树上的子树，和给定的子树是否结构一致

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) {
            queue.offer(root);
            while(!queue.isEmpty()) {//利用队列实现广度优先搜索
                TreeNode temp = queue.poll();
                //子树的根节点出现在大树上，且经过检查是子树的结构，才返回true，不然继续搜索
                if(temp.val == subRoot.val && check(temp, subRoot)) {
                    return true;
                }
                //左右子树节点不为空再入队
                if(temp.left != null) {
                    queue.add(temp.left);
                }
                if(temp.right != null) {
                    queue.add(temp.right);
                }
            }
        }
        return false;
    }

    private boolean check(TreeNode root, TreeNode subRoot) {
        //利用深度优先搜索，同时遍历两棵树，比较确定是否同构
        if(root != null && subRoot != null) {//两个节点都不为空
            return root.val == subRoot.val && check(root.left, subRoot.left) && check(root.right, subRoot.right);//值相同，左右子结点都要相同
        } else if(root == null && subRoot == null) {//都为空，那么就是同构，不然就是异构
            return true;
        }
        return false;
        //return root == null && subRoot == null ? true : false;
    }

}