leetcode.com/problems/merge-two-binary-trees/
*해결과정
Tree 2개를 합쳐야 한다. 2가지 방법이 있다.
1. DFS로 새로운 Tree를 만들고 Tree1, Tree2를 전부 더해준다.
2. 새로운 tree를 생성하지 않고 기존의 Tree1에 Tree2를 더해서 반환한다.
결국 초기조건을 잘 잡아야 하는데,
1번 같은 경우 DFS이면 Tree가 null일 때 더이상 진입을 하지 않고 return
2번 같은 경우 Tree가 null일 때 서로의 Tree를 return
*1번 방식
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if(t1==null && t2==null) return null;
TreeNode root = new TreeNode();
DFS(root,t1);
DFS(root,t2);
return root;
}
public void DFS(TreeNode root, TreeNode t1) {
if(t1==null) return;
else root.val += t1.val;
if(t1.left!=null) {
if(root.left==null){
root.left=new TreeNode();
}
DFS(root.left,t1.left);
}
if(t1.right!=null){
if(root.right==null){
root.right=new TreeNode();
}
DFS(root.right,t1.right);
}
}
}
*2번 방식
public class Solution {
public 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;
}
}
반응형
'Algorithm' 카테고리의 다른 글
897 : Increasing Order Search Tree ( leetcode / java ) (0) | 2020.10.28 |
---|---|
700 : Search in a Binary Search Tree ( leetcode / java ) (0) | 2020.10.28 |
3687 : 성냥개비 ( 백준 / java ) (0) | 2020.10.27 |
2579번 : 계단 오르기 ( 백준 / java ) (0) | 2020.10.26 |
백준 11720 / 숫자의 합 (0) | 2020.07.09 |