[Swift]LeetCode617. 合并二叉树 | Merge Two Binary Trees（合并两棵二叉树）

25-04-17 7

此处将为大家介绍关于[Swift]LeetCode617.合并二叉树|MergeTwoBinaryTrees的详细内容，并且为您解答有关合并两棵二叉树的相关问题，此外，我们还将为您介绍关于#Leetc

此处将为大家介绍关于[Swift]LeetCode617. 合并二叉树 | Merge Two Binary Trees的详细内容，并且为您解答有关合并两棵二叉树的相关问题，此外，我们还将为您介绍关于#Leetcode# 951. Flip Equivalent Binary Trees、#Leetcode# 96. Unique Binary Search Trees、19.2.27 [LeetCode 96] Unique Binary Search Trees、894. All Possible Full Binary Trees的有用信息。

本文目录一览：

[Swift]LeetCode617. 合并二叉树 | Merge Two Binary Trees（合并两棵二叉树）
#Leetcode# 951. Flip Equivalent Binary Trees
#Leetcode# 96. Unique Binary Search Trees
19.2.27 [LeetCode 96] Unique Binary Search Trees
894. All Possible Full Binary Trees

[Swift]LeetCode617. 合并二叉树 | 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.

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

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

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

Runtime: 100 ms

Memory Usage: 19.8 MB

 1 /**
 2  * DeFinition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {
16         if t1 == nil {return t2}
17         if t2 == nil {return t1}
18         var t = TreeNode(t1!.val + t2!.val)
19         t.left =  mergeTrees(t1!.left,t2!.left)
20         t.right = mergeTrees(t1!.right,t2!.right)
21         return t
22     }
23 }

120ms

 1 /**
 2  * DeFinition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {
16         switch (t1,t2) {
17         case (let t1,nil) where t1 != nil:
18             return t1!
19         case (nil,let t2) where t2 != nil:
20             return t2!
21         case (nil,nil):
22             return nil
23         default:
24             guard let tree1 = t1,let tree2 = t2 else { return nil }
25             let newTree = TreeNode(tree1.val + tree2.val)
26             newTree.left = mergeTrees(tree1.left,tree2.left)
27             newTree.right = mergeTrees(tree1.right,tree2.right)
28             return newTree
29         }
30     }
31 }

124ms

 1 /**
 2  * DeFinition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {        
16         guard let t1 = t1 else {
17             return t2
18         }
19         
20         guard let t2 = t2 else {
21             return t1
22         }
23         
24         t1.val += t2.val
25         t1.left = mergeTrees(t1.left,t2.left)
26         t1.right = mergeTrees(t1.right,t2.right)
27         return t1
28     }        
29 }

136ms

 1 /**
 2  * DeFinition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {
16             if t1 == nil && t2 == nil { return nil }
17             var newNode = TreeNode((t1?.val ?? 0) + (t2?.val ?? 0))
18 
19             if t1?.left == nil || t2?.left == nil {
20                 newNode.left = t1?.left ?? t2?.left                    
21             } else {
22                 newNode.left = mergeTrees(t1?.left,t2?.left)
23             }
24             
25             if t1?.right == nil || t2?.right == nil {
26                 newNode.right = t1?.right ?? t2?.right                    
27             } else {
28                 newNode.right = mergeTrees(t1?.right,t2?.right)
29             }
30             
31             return newNode
32     }
33 }

160ms

 1 /**
 2  * DeFinition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {
16     switch (t1,t2) {
17     case (nil,_): return t2
18     case (_,nil): return t1
19         default:
20             var treeNode: TreeNode
21             treeNode = TreeNode(t1!.val + t2!.val)
22             treeNode.left = mergeTrees(t1!.left,t2!.left)
23             treeNode.right = mergeTrees(t1!.right,t2!.right)
24             return treeNode
25         }
26     }
27 }

204ms

 1 /**
 2  * DeFinition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     var A = TreeNode(0)
16     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {
17         if t1 == nil && t2 == nil{
18             return t1
19         }else{
20             B(t1,t2,A)
21         }
22         
23         return A
24     }
25     func B(_ t1: TreeNode?,_ t2: TreeNode?,_ t3: TreeNode?)
26     {
27         if t1?.left != nil && t2?.left != nil
28         {
29             t3?.left = TreeNode(0)
30             B(t1?.left,t2?.left,t3?.left)
31         }else if t1?.left == nil && t2?.left != nil{
32             t3?.left = TreeNode(0)
33             B(nil,t3?.left)
34         }else if t1?.left != nil && t2?.left == nil{
35             t3?.left = TreeNode(0)
36             B(t1?.left,nil,t3?.left)
37         }
38         
39         if t1 != nil && t2 != nil
40         {
41             let a:Int = t1?.val as! Int
42             let b:Int = t2?.val as! Int
43             t3?.val = a + b
44         }else if t1 == nil && t2 != nil{
45             let b:Int = t2?.val as! Int
46             t3?.val = b
47         }else if t1 != nil && t2 == nil{
48             let a:Int = t1?.val as! Int
49             t3?.val = a
50         }else{
51             return
52         }
53         
54         if t1?.right != nil && t2?.right != nil
55         {
56             t3?.right = TreeNode(0)
57             B(t1?.right,t2?.right,t3?.right)
58         }else if t1?.right == nil && t2?.right != nil{
59             t3?.right = TreeNode(0)
60             B(nil,t3?.right)
61         }else if t1?.right != nil && t2?.right == nil{
62             t3?.right = TreeNode(0)
63             B(t1?.right,t3?.right)
64         }else{
65             return
66         }        
67     }
68 }

#Leetcode# 951. Flip Equivalent Binary Trees

https://leetcode.com/problems/flip-equivalent-binary-trees/

For a binary tree T,we can define a flip operation as follows: choose any node,and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Write a function that determines whether two binary trees are flip equivalent. The trees are given by root nodes root1 and root2.

Example 1:

Input: root1 = [1,2,3,4,5,6,null,7,8],root2 = [1,8,7] Output: true Explanation: We flipped at nodes with values 1,and 5.

Note:

Each tree will have at most 100 nodes.
Each value in each tree will be a unique integer in the range [0,99].

代码：

/**
 * DeFinition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 * };
 */
class Solution {
public:
    bool flipEquiv(TreeNode* root1,TreeNode* root2) {
        if(!root1 && !root2) return true;
        if(!root1 || !root2) return false;
        if(root1 -> val != root2 -> val) return false;
        return flipEquiv(root1 -> left,root2 -> right) && flipEquiv(root1 -> right,root2 -> left) ||
            flipEquiv(root1 -> left,root2 -> left) && flipEquiv(root1 -> right,root2 -> right);
    }
};

　　为什么要

这个判断

#Leetcode# 96. Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/

Given n,how many structurally unique BST‘s (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3,there are a total of 5 unique BST‘s:

   1         3     3      2      1
    \       /     /      / \           3     2     1      1   3      2
    /     /       \                    2     1         2                 3

代码：

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1,0);
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i ++) {
            for(int j = 0; j < i; j ++) 
                dp[i] += dp[j] * dp[i - j - 1];
        }
        return dp[n];
    }
};

　　卡特兰数人生中第二次遇见好吧我还是认不出

儿女情长好像也不影响我们行走江湖 FH

19.2.27 [LeetCode 96] Unique Binary Search Trees

Given n,how many structurally unique BST‘s (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3,there are a total of 5 unique BST‘s:

   1         3     3      2      1
    \       /     /      / \           3     2     1      1   3      2
    /     /       \                    2     1         2                 3

 1 class Solution {
 2 public:
 3     vector<int>q;
 4     int _numTrees(int n) {
 5         if (q[n] != -1)return q[n];
 6         int ans = 0;
 7         for (int i = 1; i <= n; i++)
 8             ans += _numTrees(i - 1) * _numTrees(n - i);
 9         q[n] = ans;
10         return ans;
11     }
12     int numTrees(int n) {
13         q=vector<int>(n+1,-1);
14         q[1] = 1; q[0] = 1;
15         return _numTrees(n);
16     }
17 };

View Code

可以用dp

894. All Possible Full Binary Trees

列出所有可能的完全二叉树

/**
 * DeFinition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        if(N%2==0)
            return {};
        int n=(N+1)/2;
        vector<TreeNode*> ans;
        if(n==1){
            ans.push_back(new TreeNode(0));
            return ans;
        }
        for(int i=1;i<=n-1;++i){
            vector<TreeNode*>  left=allPossibleFBT(2*i-1);
            vector<TreeNode*> right=allPossibleFBT(2*(n-i)-1);
            for(auto& l : left){
                for(auto& r: right){
                    TreeNode* root=new TreeNode(0);
                    root->left=l;
                    root->right=r;
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }
};

我们今天的关于[Swift]LeetCode617. 合并二叉树 | Merge Two Binary Trees和合并两棵二叉树的分享已经告一段落，感谢您的关注，如果您想了解更多关于#Leetcode# 951. Flip Equivalent Binary Trees、#Leetcode# 96. Unique Binary Search Trees、19.2.27 [LeetCode 96] Unique Binary Search Trees、894. All Possible Full Binary Trees的相关信息，请在本站查询。

本文标签：