weekly contest 36的第一题。经典的递归吧，AC率高达70%+，难道大家都很懂递归吗。。我花了大概一个小时才AC。不过做出来了还是蛮开心的，证明我的思路是对的，只有在t1 t2都不为null的时候才不建树，其余情况直接return。其实这个buildTree的过程我模仿的是Serialize and deserialize a binary tree里面的那种方法。
int value;
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
TreeNode res = dfs(t1, t2);
return res;
}
private TreeNode dfs(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return null;
}
if (t1 != null && t2 != null) {
value = t1.val + t2.val;
} else if (t2 != null) {
return t2;
} else {
return t1;
}
TreeNode node = new TreeNode(value);
node.left = mergeTrees(t1.left, t2.left);
node.right = mergeTrees(t1.right, t2.right);
return node;
}
我的if其实有点多，其实可以在所有的return之后再构造node的value。
漂亮的写法：
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;
}
}
