100. 相同的树

题目描述

链接: https://leetcode-cn.com/problems/same-tree/submissions/
给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

题目分析

和判断树的左右子树镜面性一样, 可以用两种方法(递归, 迭代)解决问题.
时间复杂度, 空间复杂度均为 O(N), O(N).

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 迭代方法, O(N), O(N)
    public boolean isSameTreeIterative(TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(p);
        stack.push(q);
        while (!stack.empty()) {
            TreeNode s = stack.pop(), t = stack.pop();
            if (s == null && t == null) continue;
            else if (s == null || t == null) return false;
            if (s.val != t.val) return false;

            stack.push(s.left);
            stack.push(t.left);
            stack.push(s.right);
            stack.push(t.right);
        }
        return true;

    }
    // 递归方法, O(N), O(N)
    public boolean isSameTreeRecursive(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        else if (p == null || q == null) return false;
        else return (p.val == q.val) && isSameTreeRecursive(p.left, q.left)
            && isSameTreeRecursive(p.right, q.right);
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //return isSameTreeRecursive(p, q);
        return isSameTreeIterative(p, q);
    }
}