Leetcode100.相同的树

Leetcode100.相同的树

题目描述

/**
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     *
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     */

思路分析

1. 判断两棵树是否相同，既要判断树的结构是否相同，还有判断对应位置的节点值是否相等
2. 使用深度优先的思路，即递归的判断当前树及其左子树是否在结构和节点值上相等
3. 判断思路
   • 先判断节点是否为空，如果为空，说明树结构相同
   • 如果节点有一个不为空，说明结构不相同
   • 然后判断节点值是否对应相等
   • 递归左子树和右子树
4. 源码见下

源码及分析

 /**
     *
     * @param p 根节点p
     * @param q 根节点q
     * @return
     * 使用深度优先的思路
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //如果两棵树都为空，则返回true
        if (p == null && q == null){
            return true;
            //否则两棵树结构不相同，返回假
        }else if (p == null || q == null){
            return false;
            //判断结构形同后，再判断值是否相等
        }else if (p.val != q.val){
            return false;
        }else {
            //递归判断左子树和右子树
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }

    }

原文：https://www.cnblogs.com/mx-info/p/15313754.html