LeetCode 344 Merge Two Binary Trees
合併兩顆二叉樹, 合併規則是相同位置的值進行相加, 返回生成後二叉樹的根節點.
例 :
輸入: Tree 1Tree 2 12 / \/ \ 3213 /\\ 547 輸出: 3 / \ 45 / \\ 547
解法
基本思路是將兩棵樹, 合併到左樹上, 基本規則是隻有當tree1
和tree2
相同位置的節點都不為空時, 才能進行相加操作, 當tree1
為空時, 把tree2
的節點嫁接
過來, 當tree2
為空時, 保留tree1
即可. 以此類推, 把每個節點都看成根節點即可.
class Solution { public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == null) { return t2; } else if (t2 == null) { return t1; } t1.val += t2.val; t1.left = mergeTrees(t1.left, t2.left); t1.right = mergeTrees(t1.right, t2.right); return t1; } }
Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Binary Trees. Memory Usage: 41.2 MB, less than 78.32% of Java online submissions for Merge Two Binary Trees.