LeetCode演算法題-Merge Two Binary Trees（Java實現）
摘要：
這是悅樂書的第274
次更新，第290
篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第142題（順位題號是617）。提供兩個二叉樹，將其合併為新的二叉樹，也可以在其中一個二叉樹上進行覆蓋。合併規則是如果兩個...
這是悅樂書的第274 次更新，第290 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第142題（順位題號是617）。提供兩個二叉樹，將其合併為新的二叉樹，也可以在其中一個二叉樹上進行覆蓋。合併規則是如果兩個節點重疊（都不為空），則將節點值加起來作為合併節點的新值。 否則，其中一個不為空的節點將用作新樹的節點。例如：
Tree 1Tree 2 12 / \/ \ 3213 /\\ 547
合併後的新二叉樹：
3 / \ 45 / \\ 547
注意：合併過程必須從兩個樹的根節點開始。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
合併兩個二叉樹，首先我們需要遍歷這兩個二叉樹的所有節點，其次是選擇遍歷順序，是前序、中序還是後序，而題目說了要從根節點開始，那麼我們選擇前序遍歷。二叉樹的常規操作有遞迴、迭代的方法，此處我們選擇遞迴的方法。
直接使用遞迴，使用前序遍歷的方式，遍歷t1和t2，順序為根節點-->左子樹-->右子樹，將每次處理的節點作為新樹的節點。此解法我是將遞迴方法獨立出來了，你也可以直接在原方法裡寫。
/**
* Definition for a binary tree node.
* public class TreeNode {
*int val;
*TreeNode left;
*TreeNode right;
*TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
return helper(t1,t2);
}
public TreeNode helper(TreeNode t1, TreeNode t2){
// 如果t1和t2的當前節點都為空，直接返回null
if (t1 == null && t2 == null) {
return null;
}
// 每次進遞迴方法裡時，都建立一個新節點，當然，你也可以用給的t1或者t2都行
TreeNode t3 = new TreeNode(0);
// 新節點的節點值
t3.val = (t1 == null ? 0 : t1.val)+(t2 == null ? 0 : t2.val);
// 新節點的左子樹
t3.left = helper(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
// 新節點的右子樹
t3.right = helper(t1 == null ? null : t1.right, t2 == null ? null : t2.right);
return t3;
}
}
03 第二種解法
使用迭代的方法，藉助棧來實現，與正常的單個二叉樹藉助棧來迭代的方法類似，只是在兩個二叉樹的情況下，多做了一些判斷。
/**
* Definition for a binary tree node.
* public class TreeNode {
*int val;
*TreeNode left;
*TreeNode right;
*TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
// 如果t1和t2都為空，直接返回null
if (t1 == null && t2 == null) {
return null;
}
// 如果t2為空，直接返回t1
if (t2 == null) {
return t1;
}
//如果t1為空，直接返回t2
if (t1 == null) {
return t2;
}
// 使用兩個棧
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
stack.push(t1);
stack2.push(t2);
while (!stack.isEmpty() || !stack2.isEmpty()) {
TreeNode temp = stack.pop();
TreeNode temp2 = stack2.pop();
if (temp == null || temp2 == null) {
continue;
}
// 將新的節點值覆蓋到t1上去
temp.val = temp.val + temp2.val;
// 如果t1的左子節點為null，那麼新的t1的左子節點直接指向t2的左子節點，否則同時入棧
if (temp.left == null) {
temp.left = temp2.left;
} else {
stack.push(temp.left);
stack2.push(temp2.left);
}
// 與上面處理左子節點情況類似
if (temp.right == null) {
temp.right = temp2.right;
} else {
stack.push(temp.right);
stack2.push(temp2.right);
}
}
return t1;
}
}
04 第三種解法
同樣是使用迭代的方法，但是我們只使用一個棧，棧中的泛型是二叉樹陣列。
/**
* Definition for a binary tree node.
* public class TreeNode {
*int val;
*TreeNode left;
*TreeNode right;
*TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
// 如果t1和t2都為空，直接返回null
if (t1 == null && t2 == null) {
return null;
}
// 如果t2為空，直接返回t1
if (t2 == null) {
return t1;
}
//如果t1為空，直接返回t2
if (t1 == null) {
return t2;
}
// 使用一個個棧
Stack<TreeNode[]> stack = new Stack<>();
stack.push(new TreeNode[]{t1, t2});
// 其中的判斷規則與上面兩個棧的方法類似
while (!stack.isEmpty()) {
TreeNode[] t = stack.pop();
if (t[0] == null || t[1] == null) {
continue;
}
t[0].val += t[1].val;
if (t[0].left == null) {
t[0].left = t[1].left;
} else {
stack.push(new TreeNode[] {t[0].left, t[1].left});
}
if (t[0].right == null) {
t[0].right = t[1].right;
} else {
stack.push(new TreeNode[] {t[0].right, t[1].right});
}
}
return t1;
}
}
05 小結
此題本質上是考察二叉樹的前序遍歷，及其遞迴、迭代兩種方法的實現，如有不熟悉的，可以去查漏補缺。
演算法專題目前已日更超過四個月 ，演算法題文章142 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！