문제: 두개의 트리를 하나의 트리로 병합할것

조건: 같은 레벨에 있는 노드의 값은 더하여 하나로 만든다. 

주의: 병합의 시작점은 두 트리의 root 부터 시작한다. 

 

두개의 트리가 병합된 모습의 예

 

2개의 트리를 모두 확인해야하기 때문에 재귀를 이용하거나 스택을 이용할 수 있다. 

재귀는 아래와 같이 구현한다. 

public class MergeTwoBinaryTrees {

    public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    	// 두개의 노드중 하나에 값이 없는 경우 체크
        if (t1 == null)
            return t2;
        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;
    }
}

'LeedCode' 카테고리의 다른 글

[LeetCode] 139. Word Break  (0) 2019.11.14
[LeetCode] 56. Merge Intervals  (0) 2019.11.13
블로그 이미지

kyungseop

공부한 내용 정리

,