100. Same Tree

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

Two binary trees are considered equal 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(q == null && p == null) return true;
        if(!checks(p,q)) return false;
        Queue<TreeNode> nodesp = new LinkedList<TreeNode>();
        nodesp.add(p);
        Queue<TreeNode> nodesq = new LinkedList<TreeNode>();
        nodesq.add(q);        
        while(!nodesp.isEmpty()){
            int n = nodesp.size();
            while(n>0){
                TreeNode currp = nodesp.poll();
                TreeNode currq = nodesq.poll();
                if(currq.val != currp.val) return false;
                if(!checks(currq.right,currp.right)) return false;
                if(!checks(currq.left,currp.left)) return false;
                if(currp.left != null){
                    nodesp.add(currp.left);
                    nodesq.add(currq.left);
                }
                if(currp.right != null){
                    nodesp.add(currp.right);
                    nodesq.add(currq.right);
                }
                n--;
            }
            
        }
        return true;
    }
    public boolean checks(TreeNode p, TreeNode q){
        if(q == null && p == null) return true;
        if((q ==null && p != null) || (p ==null && q != null)) return false;
        int a =p.val;
        int b = q.val;
        if(p.val != q.val) return false;
        return true;
    }
}

喜欢的话订阅一个呗~第一时间收到文章更新哟~

发表评论

电子邮件地址不会被公开。