100、相同的树

leetcode

Created At : 2020-07-26 00:19

Count:447 Views 👀 :

Comment:

100、相同的树
1. 示例 1:
  1. 示例 2:
  2. 示例 3:
题解
1. 1、递归判断
2. 2、迭代法层序遍历判断

100、相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

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

示例 1:

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

示例 2:

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

示例 3:

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

链接：https://leetcode-cn.com/problems/same-tree

题解

1、递归判断

/**
 * 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);
        
    }
}

2、迭代法层序遍历判断

利用双端队列进行前序遍历

class Solution {
    private boolean check(TreeNode p,TreeNode q) {
        if (p == null && q == null) {
            return null;
        }

        if (p == null || q == null) {
            return false;
        }

        if (p.val != q.val) {
            return false;
        }

        return true;
    }


    public boolean isSameTree(TreeNode p,TreeNode q) {
        if (p == null && q == null ) {
            return true;
        }

        if (!check(p,q)) return false;

        //
        ArrayDeque<TreeNode> deqP = new ArrayDeque<>();
        ArrayDeque<TreeNode> deqQ = new ArrayDeque<>();
        deqP.addLast(p);
        deqQ.addLast(q);
 
        while(!depP.isEmpty()) {
            p = deqP.removeFirst();
            q = depQ.removeFirst();

            if (!check(p,q)) {
                return false;
            }
            if (p != null) {// 两个节点都不为空
                if (!check(p.left,q.left)) {
                    return false;
                }
                // 左节点都不为空
                if (p.left != null) {
                    deqP.addLast(p.left);
                    deqQ.addLast(q.left);
                }

                if (!check(q.right,p.right)) {
                    return false;
                }
                // 右节点都不为空
                if (p.right != null) {
                    deqP.addLast(p.right);
                    deqQ.addLast(p.right);
                }
            }   
        }
        return true;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com