理解題意：相同節點位置上，都有數據的話，節點值相加，只有一方有數據的話，把有數據的部分及相關子樹保留下來。

考察操作兩棵二叉樹，二叉樹的遍歷。

一般有兩種解決方式：

????????遞歸|迭代。

區別：

????????遞歸，重復方法調用，自己調自己，進方法的棧。

????????迭代的話，自己創建一個隊列或者棧來維持狀態。

????????遞歸調用比較深的話，會內存溢出，因為要存的相關狀態太多了，所以用迭代比較好，自己創建一個棧來維護必需的信息即可。

????????沒有很深的調用層次的話，兩個差別不大。

1.遞歸?

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(Objects.isNull(root1)) return root2;if(Objects.isNull(root2)) return root1;//前序處理：結果由root1返回，不額外創建節點//其他遍歷順序，調整對應順序即可，沒啥限制//中間處理root1.val+=root2.val;//左子樹處理root1.left=mergeTrees(root1.left,root2.left);//右子樹處理root1.right=mergeTrees(root1.right,root2.right);return root1;}

?

2.迭代

public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {if(Objects.isNull(root1)) return root2;if(Objects.isNull(root2)) return root1;//自定義棧，保存要處理的節點，處理后pop彈出，處理完時，棧空Stack<TreeNode> stack=new Stack<>();//這個入棧順序是因為棧先進后出stack.push(root2);stack.push(root1);while(!stack.isEmpty()) {TreeNode node1=stack.pop();TreeNode node2=stack.pop();//根節點處理node1.val+= node2.val;//非空節點入棧if(node1.left!=null&&node2.left!=null){stack.push(node2.left);stack.push(node1.left);}if(node1.right!=null&&node2.right!=null){stack.push(node2.right);stack.push(node1.right);}//結果由root1返回，root1缺失的部分，root2補全if(node1.left==null&&node2.left!=null){node1.left=node2.left;}if(node1.right==null&&node2.right!=null){node1.right=node2.right;}}return root1;}

優化的余地

            //非空節點入棧if(node1.left!=null&&node2.left!=null){stack.push(node2.left);stack.push(node1.left);}if(node1.right!=null&&node2.right!=null){stack.push(node2.right);stack.push(node1.right);}//結果由root1返回，root1缺失的部分，root2補全if(node1.left==null&&node2.left!=null){node1.left=node2.left;}if(node1.right==null&&node2.right!=null){node1.right=node2.right;}-------------------------分界線--------------------------------------//非空節點入棧if(node1.left!=null&&node2.left!=null){stack.push(node2.left);stack.push(node1.left);}else if(node1.left==null){ //結果由root1返回，root1缺失的部分，root2補全node1.left=node2.left;}if(node1.right!=null&&node2.right!=null){stack.push(node2.right);stack.push(node1.right);}else if(node1.right==null){node1.right=node2.right;}

3.時間復雜度分析

1.遞歸

? ? ? ? 時間復雜度：O(n)

? ? ? ? 空間復雜度：O(1)

2.迭代

? ? ? ? 時間復雜度：O(n)

? ? ? ? 空間復雜度：O(n)