题目

Given two binary trees,write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

解法一

思路

先序遍历的递归

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p,TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val)
            return false;
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

解法二

思路

用栈或者队列来实现层次遍历，一个栈（队列） 或者 两个栈（队列）都可以。如果用一个栈（队列），那就是两棵树同一个位置的节点同时入栈，出栈的时候同时出栈，然后进行对比。以下用一个队列实现。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p,TreeNode q) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(p);
        queue.addLast(q);
        while(!queue.isEmpty()){
            p = queue.removeFirst();
            q = queue.removeFirst();
            
            if(p == null && q == null)
                continue;
            else if(p == null || q == null || q.val!=p.val)
                return false;
            else {
                queue.addLast(p.left);
                queue.addLast(q.left);
                queue.addLast(p.right);
                queue.addLast(q.right);
            }
        }
        return true;
    }
}