首页 软件代码

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和注释。





文章评论

    马内 访客ChromeWindows
    2021-08-3 8:30   回复

    数据算法,学习了

目录