题解 | #合并二叉树#

关键是要想到 Stack 里的元素用的 1v3 数组，气死个人

stack.push(new TreeNode[] {t1, t2, merged});

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
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        // 合并当前节点
        TreeNode merged = new TreeNode(t1.val + t2.val);

        // 递归合并左右子树
        // merged.left = mergeTrees(t1.left,t2.left);
        // merged.right = mergeTrees(t1.right,t2.right);

        // 迭代
        Stack<TreeNode[]> stack = new Stack<>();
        stack.push(new TreeNode[] {t1, t2, merged}); // {t1, t2, merged}
        while (!stack.isEmpty()) {
            TreeNode[] nodes = stack.pop();
            TreeNode node1 = nodes[0];
            TreeNode node2 = nodes[1];
            TreeNode mergedNode = nodes[2];

            // 合并left
            if (node1.left != null || node2.left != null) {
                TreeNode leftNode = node1.left == null ? new TreeNode(0) : node1.left;
                TreeNode rightNode = node2.left == null ? new TreeNode(0) : node2.left;
                mergedNode.left = new TreeNode(leftNode.val + rightNode.val);
                stack.push(new TreeNode[] {leftNode, rightNode, mergedNode.left});
            }
            // 合并right
            if (node1.right != null || node2.right != null) {
                TreeNode leftNode = node1.right == null ? new TreeNode(0) : node1.right;
                TreeNode rightNode = node2.right == null ? new TreeNode(0) : node2.right;
                mergedNode.right = new TreeNode(leftNode.val + rightNode.val);
                stack.push(new TreeNode[] {leftNode, rightNode, mergedNode.right});
            }
        }

        return merged;// 返回合并后的根节点
    }
}