.leetcode(617. Merge Two Binary Trees)

https://leetcode.com/problems/merge-two-binary-trees

 

2. 2021.01.09 시도

소요시간: 17분(recursive)

// recursive
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        TreeNode ret = recursive(root1, root2);
        return ret;
    }
    
    private TreeNode recursive(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return copyTreeNode(root2);
        }
        if (root2 == null) {
            return copyTreeNode(root1);
        }

        TreeNode ret = new TreeNode();
        ret.val = root1.val + root2.val;
        ret.left = recursive(root1.left, root2.left);
        ret.right = recursive(root1.right, root2.right);
        
        return ret;
    }
    
    private TreeNode copyTreeNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        TreeNode ret = new TreeNode();
        ret.val = root.val;
        ret.left = copyTreeNode(root.left);
        ret.right = copyTreeNode(root.right);
        
        return ret;
    }
}

풀이 접근 과정

순회가 필요하니 recursive나 iterative를 써야겠다. 좀 더 직관적인 recursive를 사용하자.

새로운 값이 아닌 root1에 있는거 더하고 없는거는 붙이면 되겠다. root1에서는 null인데 root2가 있다면 root2를 그대로 붙여도 되겠구나 했다. 그리고 풀었다. 그런데 문제에 보니 "You need to merge the two trees into a new binary tree." 라고 적혀있어서 아예 다 새로운 트리노드로 리턴되도록 추가 구현하였다. 

구현은 쉽게 copyTreeNode메소드를 하나 만들었다. root1 혹은 root2가 null인 순간 그 tree를 그대로 복제할 수 있게 하였다. 그리고 기본적으로 recursive를 타면서 val를 더해줄 때 treeNode를 생성해서 기존 파라미터와 독립된 treeNode를 리턴할 수 있게 하였다.

 

느낀점

• recursive하게 푸는게 더 익숙하니 일단 recursive하게 풀고 iterative하게 푸는게 좋은거 같다.
• iterative하게 하려면 새로운 변수를 함께 넘겨주어야한다. 이게 iterative하게 푸는 포인트다. 더불어 treeNode를 iterative하게 복사하는 방법도 똑같은 방식으로 적용된다. 이를 코드로 작성해보았다.

// iterative dfs
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return copyTreeNode(root2);
        }
        
        if (root2 == null) {
            return copyTreeNode(root1);
        }
        
        TreeNode ret = new TreeNode();
        LinkedList<TreeNode[]> stack = new LinkedList<>();
        stack.add(new TreeNode[]{root1, root2, ret});
        
        while(!stack.isEmpty()) {
            TreeNode[] nodes = stack.pop();
            
            if (nodes[0] == null || nodes[1] == null) {
                nodes[2] = null;
                continue;
            }
            
            nodes[2].val = nodes[0].val + nodes[1].val;
            if (nodes[0].left == null) {
                nodes[2].left = copyTreeNode(nodes[1].left);
            } else if (nodes[1].left == null) {
                nodes[2].left = copyTreeNode(nodes[0].left);
            } else {
                nodes[2].left = new TreeNode();
                stack.push(new TreeNode[]{nodes[0].left, nodes[1].left, nodes[2].left});
            }
            
            if (nodes[0].right == null) {
                nodes[2].right = copyTreeNode(nodes[1].right);
            } else if (nodes[1].right == null) {
                nodes[2].right = copyTreeNode(nodes[0].right);
            } else {
                nodes[2].right = new TreeNode();
                stack.push(new TreeNode[]{nodes[0].right, nodes[1].right, nodes[2].right});
            }
        }
        
        return ret;
    }
    
    private TreeNode copyTreeNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode ret = new TreeNode();
        
        LinkedList<TreeNode[]> stack = new LinkedList<>();
        stack.add(new TreeNode[]{root, ret});
        
        while(!stack.isEmpty()) {
            TreeNode[] nodes = stack.pop();
            
            if (nodes[1] == null) {
                nodes[2] = null;
                continue;
            }
            
            nodes[1].val = nodes[0].val;
            if (nodes[0].left != null) {
                nodes[1].left = new TreeNode();
                stack.push(new TreeNode[]{nodes[0].left , nodes[1].left});
            }
            
            if (nodes[0].right != null) {
                nodes[1].right = new TreeNode();
                stack.push(new TreeNode[]{nodes[0].right , nodes[1].right});
            }
        }
        
        return ret;
    }
}

• 처음 시도할 때 내용을 보니 새로운 바이너리 트리를 만들어야겠다는 생가은 아예 하지 못했떤것으로 보인다.
• 위에는 dfs로 구했는데 bfs는 쉽게 queue로 바꿔주면 된다. 지금 문제는 순서에 크기 관련이 없어서 쉽게 치환할 수 있다.

// iterative bfs
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return copyTreeNode(root2);
        }
        
        if (root2 == null) {
            return copyTreeNode(root1);
        }
        
        TreeNode ret = new TreeNode();
        LinkedList<TreeNode[]> queue = new LinkedList<>();
        queue.push(new TreeNode[]{root1, root2, ret});
        
        while(!queue.isEmpty()) {
            TreeNode[] nodes = queue.poll();
            
            if (nodes[0] == null || nodes[1] == null) {
                nodes[2] = null;
                continue;
            }
            
            nodes[2].val = nodes[0].val + nodes[1].val;
            if (nodes[0].left == null) {
                nodes[2].left = copyTreeNode(nodes[1].left);
            } else if (nodes[1].left == null) {
                nodes[2].left = copyTreeNode(nodes[0].left);
            } else {
                nodes[2].left = new TreeNode();
                queue.push(new TreeNode[]{nodes[0].left, nodes[1].left, nodes[2].left});
            }
            
            if (nodes[0].right == null) {
                nodes[2].right = copyTreeNode(nodes[1].right);
            } else if (nodes[1].right == null) {
                nodes[2].right = copyTreeNode(nodes[0].right);
            } else {
                nodes[2].right = new TreeNode();
                queue.push(new TreeNode[]{nodes[0].right, nodes[1].right, nodes[2].right});
            }
        }
        
        return ret;
    }
    
    private TreeNode copyTreeNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode ret = new TreeNode();
        
        LinkedList<TreeNode[]> queue = new LinkedList<>();
        queue.push(new TreeNode[]{root, ret});
        
        while(!queue.isEmpty()) {
            TreeNode[] nodes = queue.poll();
            
            if (nodes[1] == null) {
                nodes[2] = null;
                continue;
            }
            
            nodes[1].val = nodes[0].val;
            if (nodes[0].left != null) {
                nodes[1].left = new TreeNode();
                queue.push(new TreeNode[]{nodes[0].left , nodes[1].left});
            }
            
            if (nodes[0].right != null) {
                nodes[1].right = new TreeNode();
                queue.push(new TreeNode[]{nodes[0].right , nodes[1].right});
            }
        }
        
        return ret;
    }
}

 

 

1. 2021.01.01 시도

소요시간: 19분

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }

        int t1val = t1 == null ? 0 : t1.val;
        int t2val = t2 == null ? 0 : t2.val;
        int sumval = t1val + t2val;

        TreeNode sumTree = new TreeNode(sumval);
        sumTree.left = 
            mergeTrees(t1 == null? null: t1.left, t2 == null? null: t2.left);
        sumTree.right =
            mergeTrees(t1 == null? null: t1.right, t2 == null? null: t2.right);
        return sumTree;
    }
}

풀이 접근 과정

TreeNode구조체를 잘 익혀둬야겠다. left, right, val 형태를 이용해서 풀자

다 더하면 되겠다. 돌면서 null체크만 잘하면 통과하겠다.

tree다 보니 left, right를 꼭 로직에 넣어야겠다.

시간복잡도는 tree이기때문에 nlogN 이정도 걸릴거 같다.(실제로 아니었음)
void 함수를 만들어서 ref를 파라미터로 넘기고 val만 업데이트 해주면되지 않을까했다.

 

느낀점

1. (문제 풀기 전 5번)처럼 생각했는데 일단 우선은 메소드를 만들기전에 return으로 문제에 필요한 로직을 완성할 수 있는지 생각해보았다. 그리고 결국 메소드 없이 해결되었다.
2. 문제에서 보면 정수인지 자연수인지에 대한 내용이 있는데 없는걸 보고 상관하지 않아도 되는 문제라고 생각했다.
3. 로직을 먼저 만들까, 아니면 종료조건을 먼저 만들까 고민되었는데 조건을 먼저 시도해보는게 좋다고 생각했다. 로직을 할때 종료조건에 따라 다음 메소드로 넘어가는 파라미터가 결정되기때문에 자꾸 다시 조건을 생각하게 된다. 따라서 조건 먼저 생각해보고 시도하는게 좋을거라고 판단하였다.
4. traverse를 하는거여서 시간복잡도는 N정도만 걸렸다.
5. 나같은 경우, 새로운 메모리 sumTree를 만들어 사용했는데 그냥 일방적으로 t1에 더한값을 덮어씌우면 공간절약은 할 수 있다. 물론 주어진 데이터를 변화시키는 방법이라 선호하지는 않는다. 그런데 t1, t2가 하나가 null이면 다른 하나의 값을 그대로 써버리는 로직으로 하면 좀 더 빠르게 끝날 수 있었던건 솔직히 생각 못 했다. if(t1==null) return t2; 와 같은건 기발하다.
6. 이런 tree덧셈하는 방식에 input value를 수정해도 된다고 하면 2가지 방법이 있다는걸 알았다. 하나는 내가 사용한 Recursion이고 하나는 stack을 사용해서 Iterative하게 푸는 방식이다.

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        Stack<TreeNode[]> stack = new Stack();
        stack.push(new TreeNode[]{ t1, t2 });

        while (!stack.isEmpty()) {
            TreeNode[] treeNodes = stack.pop();
            if (treeNodes[1] == null) {
                continue;
            }

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

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

        }    
        return t1;
    }
}

 

 

참고

• backTracking vs recursion: https://stackoverflow.com/questions/26670757/difference-between-backtracking-and-recursion/26671095

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형