617. Merge Two Binary Trees

Posted on | Edited on | Views:

LeetCode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1==null) return t2;
        else if(t2==null) return t1;
        else{
            TreeNode newNode=new TreeNode(t1.val+t2.val);
            newNode.left=mergeTrees(t1.left,t2.left);
            newNode.right=mergeTrees(t1.right,t2.right);
            return newNode;
        }
    }
}

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2){
        if(t1==null) return t2;
        else if(t2==null) return t1;
        else{
            LinkedList<TreeNode[]> stack=new LinkedList<>();
            stack.push(new TreeNode[]{t1,t2});
            while(!stack.isEmpty()){
                TreeNode[] tmpNode=stack.pop();
                if(tmpNode[0]==null||tmpNode[1]==null){
                    continue;
                }

                tmpNode[0].val=tmpNode[0].val+tmpNode[1].val;

                if(tmpNode[0].left==null){
                    tmpNode[0].left=tmpNode[1].left;
                }else{
                    stack.push(new TreeNode[]{tmpNode[0].left,tmpNode[1].left});
                }

                if(tmpNode[0].right==null){
                    tmpNode[0].right=tmpNode[1].right;
                }else{
                    stack.push(new TreeNode[]{tmpNode[0].right,tmpNode[1].right});
                }
            }
        }
        return t1;
    }
}

0%