LeetCode-算法-广度和深度优先搜索-第8天

617. 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
实例1：

输入: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
         3
        / \
       4   5
      / \   \ 
     5   4   7

具体题目连接

Python

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1:
            return  root2
        if not root2:
            return  root1
        node=TreeNode(root1.val+root2.val)
        node.left=self.mergeTrees(root1.left,root2.left)
        node.right=self.mergeTrees(root1.right,root2.right)
        return node

思路：采用深度优先搜索方法进行，因为对于二叉树而言，深度比广度更简洁易懂。

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1:
            return root2
        elif not root2:
            return root1
        node=TreeNode(root1.val+root2.val)
        node_0=collections.deque([node])#记录node节点
        node_1=collections.deque([root1])#
        node_2=collections.deque([root2])
        while node_1 and node_2:
            node0= node_0.popleft()
            node1 = node_1.popleft()
            node2 = node_2.popleft()
            left1, right1 = node1.left, node1.right
            left2, right2 = node2.left, node2.right
            if left1 or left2:
                if left1 and left2:
                    left = TreeNode(left1.val + left2.val)
                    node0.left = left
                    node_0.append(left)
                    node_1.append(left1)
                    node_2.append(left2)
                elif left1:
                    node0.left = left1
                elif left2:
                    node0.left = left2
            if right1 or right2:
                if right1 and right2:
                    right = TreeNode(right1.val + right2.val)
                    node0.right=right
                    node_0.append(right)
                    node_1.append(right1)
                    node_2.append(right2)
                elif right1:
                    node0.right = right1
                elif right2:
                    node0.right = right2      
        return node

思路：采用广度优先搜索，因此每一次进行合并必须保证每一层结束后才能进行下一层，因此需要采用三个队列储存相应节点，并统计每一层的个数。

GO

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1==nil{
        return root2
    }
    if root2==nil{
        return root1
    }
    var node TreeNode
    node.Val=root1.Val+root2.Val
    node.Left=mergeTrees(root1.Left,root2.Left)
    node.Right=mergeTrees(root1.Right,root2.Right)
    return &node
}
思路：可看python深度优先搜索。

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

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
具体题目链接

Python

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        que=collections.deque([root])
        while que:
            size=len(que)
            for i in range(size):
                node = que.popleft()
                # 连接
                if i < size - 1:
                    node.next = que[0]
                
                # 拓展下一层节点
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return root

思路：昨天太累了，就一直没手写一边。只是看懂了思路。通过父节点层采用使用已建立的next 指针来实现下一层的链接。
那就分为两种情况，一种是同一父节点形式。那么：node.left.next = node.right就完成了指向。（黑色箭头）
另一种形式是不同父节点的指向，那么就需要通过父节点的node.next来实现node.right.next = node.next.left。（红色箭头）

GO

func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    //leftmost获取每一层的最左侧节点（相当于层循环）
    for leftmost := root; leftmost.Left != nil; leftmost = leftmost.Left {
        //node则循环一层的节点，并操作子节点进行连接、
        for node := leftmost; node != nil; node = node.Next {
            node.Left.Next = node.Right//同一父节点的子节点相连。
            if node.Next != nil {
                node.Right.Next = node.Next.Left//不同父节点的子节点相连，通过node实现。
            }
        }
    }

    // 返回根节点
    return root
}

思路：参考python和注释。