算法入门第八天

617. 合并二叉树

简单的合并二叉树，我没做出来，哈哈。。

/**
 *
 617. 合并二叉树
 给你两棵二叉树： root1 和 root2 。

 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

 返回合并后的二叉树。

 注意: 合并过程必须从两个树的根节点开始。



 示例 1：


 输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
 输出：[3,4,5,5,4,null,7]
 示例 2：

 输入：root1 = [1], root2 = [1,2]
 输出：[2,2]


 提示：

 两棵树中的节点数目在范围 [0, 2000] 内
 -10^4 <= Node.val <= 10^4


 * @author zeroheart
 *
 */
public class Question617 {
   public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
      if(root1 == null) return root2;
      if(root2 == null) return root1;
      root1.val += root2.val;
      root1.left = mergeTrees(root1.left, root2.left);
      root1.right = mergeTrees(root1.right, root2.right);
      return root1;
   }

   public static void main(String[] args) {
   }

}

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

这题目看着简单，实际费点脑子的，原理就是一层一层的遍历，要写出来还是不容易。。太菜了

/**
 *
 116. 填充每个节点的下一个右侧节点指针
 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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

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



 示例 1：



 输入：root = [1,2,3,4,5,6,7]
 输出：[1,#,2,3,#,4,5,6,7,#]
 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
 示例 2:

 输入：root = []
 输出：[]


 提示：

 树中节点的数量在 [0, 212 - 1] 范围内
 -1000 <= node.val <= 1000

 * @author zeroheart
 *
 */
public class Question116 {
   public Node connect(Node root) {
      if(root == null) return root;
      Node leftMost = root;
      while (leftMost.left!=null){
         Node head = leftMost;
         while (head!=null){
            // 进来，直接连左边和右边
            head.left.next = head.right;
            // root来说，这里是空的
            if (head.next != null) {
               head.right.next = head.next.left;
            }
            head = head.next; // 对于root，跳到下一次，其他的往后移一个
         }
         leftMost = leftMost.left;  // 下一层，最左边
      }
      return root;
   }

   public static void main(String[] args) {
   }

}