weekly contest 36的第一題。經(jīng)典的遞歸吧晴弃，AC率高達(dá)70%+掩幢，難道大家都很懂遞歸嗎。上鞠。我花了大概一個(gè)小時(shí)才AC际邻。不過做出來了還是蠻開心的，證明我的思路是對的芍阎，只有在t1 t2都不為null的時(shí)候才不建樹世曾，其余情況直接return。其實(shí)這個(gè)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其實(shí)有點(diǎn)多度硝，其實(shí)可以在所有的return之后再構(gòu)造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;
}
}
