2021.11.13 - SX07-22.合并二叉树

• 1. 题目
• 2. 思路
• • (1) 递归
  • (2) 迭代
• 3. 代码

• 总体思想是新建一颗树。
• 当两棵树的根结点均不为null时，新建一个结点，值为两棵树的根结点的值之和；当任意一颗树的根结点为null时，返回另一颗树的根结点即可。

• 总体思想是将二叉树2合并到二叉树1上。
• 当两棵树的根结点均不为null时，全部入栈；当二叉树1的根结点为null，二叉树2的根结点不为null时，将二叉树2的根结点接到二叉树1上即可。

import java.util.Deque;
import java.util.linkedList;
import java.util.Stack;

public class Test {
    public static void main(String[] args) {
    }
}

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;
    }
}

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        return root;
    }
}

class Solution1 {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        Deque stack = new linkedList<>();
        stack.push(root2);
        stack.push(root1);
        while (!stack.isEmpty()) {
            TreeNode node1 = stack.pop();
            TreeNode node2 = stack.pop();
            node1.val += node2.val;
            if (node1.right != null && node2.right != null) {
                stack.push(node2.right);
                stack.push(node1.right);
            } else {
                if (node1.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) {
                    node1.left = node2.left;
                }
            }
        }
        return root1;
    }
}