[数据结构与算法]6.18 合并二叉树——【LeetCode】

package com.xxxx.test;

import java.util.LinkedList;
import java.util.Stack;

class Solution {
	//方法一：递归
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    	//按照前序遍历的方式
    	if(root1 == null){
    		return root2;
    	}
    	if(root2 == null){
    		return root1;
    	}
    	
    	TreeNode newRoot = new TreeNode(root1.val + root2.val);
    	newRoot.left = mergeTrees(root1.left, root2.left);
    	newRoot.right = mergeTrees(root1.right, root2.right);
    	return newRoot;
    }
    
    //方法二：迭代  使用队列
    public TreeNode mergeTrees1(TreeNode root1, TreeNode root2) {
    	if(root1 == null){
    		return root2;
    	}
    	if(root2 == null){
    		return root1;
    	}
    	
    	LinkedList<TreeNode> queue = new LinkedList<>();
    	queue.offer(root1);
    	queue.offer(root2);
    	while(!queue.isEmpty()){
    		TreeNode node1 = queue.poll();
    		TreeNode node2 = queue.poll();
    		// 此时两个节点一定不为空，val相加
    		node1.val = node1.val + node2.val;
    		// 如果两棵树左节点都不为空，加入队列
    		if(node1.left != null && node2.left != null){
    			queue.offer(node1.left);
    			queue.offer(node2.left);
    		}
    		// 如果两棵树右节点都不为空，加入队列
    		if(node1.right != null && node2.right != null){
    			queue.offer(node1.right);
    			queue.offer(node2.right);
    		}
    		// 若node1的左节点为空，直接赋值
    		if(node1.left == null && node2.left != null){
    			node1.left = node2.left;
    		}
    		// 若node1的右节点为空，直接赋值
    		if(node1.right == null && node2.right != null){
    			node1.right = node2.right;
    		}
    		// node1左右结点不为空，node2左右结点为空的情况  默认不做处理
    	}
    	
    	return root1;
    }
    
    
    // 迭代    --- 使用栈
    public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {
    	if(root1 == null){
    		return root2;
    	}
    	if(root2 == null){
    		return root1;
    	}
    	
    	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(node2.right != null && node1.right != null){
    			stack.push(node2.right);
    			stack.push(node1.right);
    		}else{
    			if(node1.right == null){
    				node1.right = node2.right;
    			}
    			//还有一种情况 node2.right == null 此时不做处理
    		}
    		
    		if(node2.left != null && node1.left != null){
    			stack.push(node2.left);
    			stack.push(node1.left);
    		}else{
    			if(node1.left == null){
    				node1.left = node2.left;
    			}
    			//还有一种情况 node1.right == null 此时不做处理
    		}
    	}
    	return root1;	
    }
    
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode() {}
	TreeNode(int val) { this.val = val; }
	TreeNode(int val, TreeNode left, TreeNode right) {
	     this.val = val;
	     this.left = left;
	     this.right = right;
	}
}