题解 | #合并二叉树#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param t1 TreeNode类
     * @param t2 TreeNode类
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here

        // 根据左程云老师讲的【二叉树递归套路】，先弄明白三件事
        // 1.我要干什么：
        //        令root.left   ->   【左子树】的【完整形态的根节点】
        //        令root.right  ->   【右子树】的【完整形态的根节点】

        // 2.我需要什么信息：
        //      综上所述，我需要左右子树的【完整形态的根节点】

        // 3.我如何利用两个子树的信息加工出来我的信息：
        //      将root.left和root.right分别指向了正确的完整子树根节点后，【root】本身就是这个子树的完整根节点

        return process(t1, t2);
    }

    // 递归序遍历二叉树函数 - 返回当前子树下的merge后的完整根节点
    public TreeNode process(TreeNode t1, TreeNode t2) {
        // 递归出口
        if (t2 == null) {
            // t2空，说明没有什么可修改或补充t1的了，因此没有继续下去的必要了
            return t1;
        }
        if (t1 == null) {
            // t1空，而t2非空，返回t2作为上一层的子树，相当于补充t1了
            // 踩坑！这里如果采用的是“public 【void】 process(TreeNode t1, TreeNode t2)”就会出问题
            // 因为t1是null，如果令t1 = t2，那么这个t2【并不能】作为子树返回给上一层的t1
            // 所以这里采取将TreeNode对象返回，由上一层亲自将左右结点指向它，保证没问题
            return t2;
        }
        // t1非空，且t2非空
        t1.val += t2.val;

        // 令t1的左右指针分别指向左右两个完整子树的根节点
        t1.left = process(t1.left, t2.left);
        t1.right = process(t1.right, t2.right);
        return t1;
    }
}