题目描述: 给予两个二叉树 t1 , t2 , 合并他们.
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.
思路:
1, 输入 t1 t2, 判断是否都为 null , 如果是 则返回 null
2, 判断 t1 t2 是否都不为 null , 如果是 则 t1.val += t2.val
3, 否则判断 t1 == null && t2 != null , 如果是 则 t1 = new TreeNode(t2.val)
4, 如果 t2 !=null 那么说明 t2 可能还有子节点可以合并到 t1 , 于是进行递归
- t1.left = mergeTrees(t1.left, t2.left)
- t1.right = mergeTrees(t1.right, t2.right)
5, 返回 t1
每次递归都是只针对一个节点的合并
完整代码:
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
- // 思路
- // 1. 输入 t1 t2 判断是否都为 null, 如果是则返回 null
- // 2. 如果 t1 t2 都不为 null 那么 t1.val += t2.val
- // 3. 如果 t1 == null t2!=null 那么就在 t1 创建一个节点, 值为 t2.val
- // 4. 如果 t2 !=null 那么就进行递归,
- // t1.left = mergeTrees(t1.left, t2.left)
- // t1.right = mergeTrees(t1.right, t2.right)
- // 5. 返回 t1
- if(t1 == null && t2 == null)
- return null;
- if(t1 != null && t2 != null){
- t1.val += t2.val;
- }else if(t1 == null && t2 != null){
- t1 = new TreeNode(t2.val);
- }
- if(t2 !=null){
- t1.left = mergeTrees(t1.left, t2.left);
- t1.right = mergeTrees(t1.right, t2.right);
- }
- return t1;
- }
- }
来源: http://www.bubuko.com/infodetail-3357186.html