算法基础第七天

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

这是116题的普遍解法，适用于116，116是特殊的二叉树，这个是普通的二叉树

/**
 117. 填充每个节点的下一个右侧节点指针 II
 给定一个二叉树

 struct Node {
 int val;
 Node *left;
 Node *right;
 Node *next;
 }
 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

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



 进阶：

 你只能使用常量级额外空间。
 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。


 示例：



 输入：root = [1,2,3,4,5,null,7]
 输出：[1,#,2,3,#,4,5,7,#]
 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。


 提示：

 树中的节点数小于 6000
 -100 <= node.val <= 100


 * @author zeroheart
 *
 */
public class Question117 {

    public Node connect(Node root) {

        //相比116来说，这是普遍情况，116是特殊的二叉树，116. 填充每个节点的下一个右侧节点指针

        if(root == null) return root;
        Node cur = root;
        while (cur!=null){
            Node dummy = new Node(0);
            Node pre = dummy;

            while (cur != null) {
                // 一层中的每一个
                if (cur.left != null) {
                    pre.next = cur.left;
                    pre = pre.next;
                }

                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = pre.next;
                }
                cur = cur.next;
            }

            cur = dummy.next; // 下一层的第一个
        }

        return root;
    }

}

572. 另一棵树的子树

这题可以提取出来一个同一个树的函数。

/**
 572. 另一棵树的子树
 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。



 示例 1：


 输入：root = [3,4,5,1,2], subRoot = [4,1,2]
 输出：true
 示例 2：


 输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
 输出：false


 提示：

 root 树上的节点数量范围是 [1, 2000]
 subRoot 树上的节点数量范围是 [1, 1000]
 -10^4 <= root.val <= 10^4
 -10^4 <= subRoot.val <= 10^4


 * @author zeroheart
 *
 */
public class Question572 {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null && subRoot == null) return true;
        if(root == null || subRoot == null) return false;

        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot) || isSameTree(root, subRoot);
    }


    public boolean isSameTree(TreeNode root, TreeNode subRoot) {
        if(root==null && subRoot==null)return true;
        if(root==null || subRoot==null)return false;

        if(root.val != subRoot.val) return false;

        return isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right);
    }



}