题解 | #【冲刺双百】合并二叉树#

思路

二叉树题目逃不过遍历框架，我们需要确定的在遍历过程中需要做什么以及在何时做

1. 同步遍历两棵二叉树，保证每次遍历的点为相互对应的（我们以覆盖树1为例）
2. 合并二叉树有如下情形：
   • 两结点均不为空：结点值相加，覆盖树1结点；继续遍历
   • 树1结点为空，树2结点不为空：因为我们约定了覆盖树1，所以应当将树2结点及其子树一起移动到树1对应位置（这里需要记录树1空结点的父节点以及该空结点是左孩子还是右孩子）；继续遍历
   • 树1结点不为空，树2结点为空：不需要做什么，继续遍历即可
   • 两结点均为空：同样不需要做什么，继续便利即可
3. 遍历时，为了记录当前树1结点的父节点及左/右，我们在遍历函数的参数中维护这两个值，详见代码

代码

public class Solution {

    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if(t1==null) return t2;
        if(t2==null) return t1;
        travel(null, true, t1, t2);
        return t1;
    }
   /**
     * @param fot1 t1的父节点
     * @param w 取值为true时代表t1为左孩子
     * @param t1  
     * @param t2  
     */
    public void travel(TreeNode fot1, boolean w, TreeNode t1, TreeNode t2){
    	//如果两结点都为空
        if(t1==null&&t2==null) return;
        //如果t1空而t2不空
        if(t1==null){
            if(w) fot1.left=t2;
            else fot1.right=t2;
            return;
        }
        //如果t2空而t1不空
        if(t2==null){
            return ;
        } 
        //如果均不为空
        t1.val+=t2.val;
        //遍历左孩子
        travel(t1, true, t1.left, t2.left);
        //遍历右孩子
        travel(t1, false, t1.right, t2.right);
    }
    
}