合并兩棵二叉樹

enda 發布于2019-07-25 12:03 / 843人閱讀

摘要：合并兩棵二叉樹思路遇到樹問題，首先想到遞歸將的加到，返回當前處理的結點如果為，把引用指向需要注意處理的問題代碼本題以及其它題目代碼地址地址

合并兩棵二叉樹 Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input: 
    Tree 1                     Tree 2                  
          1                         2                             
         /                        /                             
        3   2                     1   3                        
       /                                                    
      5                             4   7                  
Output: 
Merged tree:
         3
        / 
       4   5
      /     
     5   4   7

Note: The merging process must start from the root nodes of both trees.

思路

遇到樹問題，首先想到遞歸

將t2的val加到t1，返回當前處理的t1結點

如果t1為null，把引用指向t2

需要注意處理null的問題

代碼

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        if t1 is not None and t2 is not None:
            t1.val += t2.val
            t1.left = self.mergeTrees(t1.left, t2.left)
            t1.right = self.mergeTrees(t1.right, t2.right)
        elif t1 is None and t2 is not None:
            t1 = t2
        return t1

本題以及其它leetcode題目代碼github地址: github地址

GPU云服務器云服務器二叉樹 python二叉樹平衡二叉樹實現二叉樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/38650.html

二叉樹那些事兒

摘要：大家在聊到二叉樹的時候，總會離不開鏈表。受限線性表主要包括棧和隊列，受限表示對結點的操作受限制。存儲結構線性表主要由順序表示或鏈式表示。鏈式表示指的是用一組任意的存儲單元存儲線性表中的數據元素，稱為線性表的鏈式存儲結構。大家在聊到二叉樹的時候，總會離不開鏈表。這里先帶大家一起了解一些基本概念。線性表概念線性表是最基本、最簡單、也是最常用的一種數據結構。線性表中數據元素之間的關...

Little_XM 2019-08-22 16:28 評論0 收藏0
【數據結構_浙江大學MOOC】第三四五講樹

摘要：然而，一棵給定的二叉搜索樹卻可以由多種不同的插入序列得到。輸出格式對每一組需要檢查的序列，如果其生成的二叉搜索樹跟對應的初始序列生成的一樣，輸出，否則輸出。本篇為關于樹的編程題，給出編譯器 C++(g++)的解答。主要記錄題意理解和代碼學習過程。 1 樹的同構題目給定兩棵樹T1和T2。如果T1可以通過若干次左右孩子互換就變成T2，則我們稱兩棵樹是同構的。例如圖1給出的兩棵樹就是...

happyfish 2019-07-31 11:12 評論0 收藏0
【LeetCode 二叉樹專項】尋找重復的子樹（652）

摘要：文章目錄題目示例說明限制解法一分析實現復雜度題目給定一棵二叉樹的根節點，請返回所有的重復子樹。示例示例輸入輸出示例輸入輸出示例輸入輸出說明來源力扣鏈接限制二叉樹中的節點數量在之間。 ...

leejan97 2021-11-15 11:38 評論0 收藏0
tweaked identical binary tree

摘要：原題檢查兩棵二叉樹是否在經過若干次扭轉后可以等價。扭轉的定義是，交換任意節點的左右子樹。等價的定義是，兩棵二叉樹必須為相同的結構，并且對應位置上的節點的值要相等。樣例是扭轉后可等價的二叉樹。原題檢查兩棵二叉樹是否在經過若干次扭轉后可以等價。扭轉的定義是，交換任意節點的左右子樹。等價的定義是，兩棵二叉樹必須為相同的結構，并且對應位置上的節點的值要相等。注意：你可以假設二叉樹中不會有重復...

frontoldman 2019-08-14 17:07 評論0 收藏0