LeetCode——相同的树

NO.100 相同的树 简单

思路一：递归逐个节点比较

做题的时候看到了labuladong大神的一篇关于二叉树的文章，真的是太通透了！文章传送门。

开始说本题的题解：先有二叉树的框架：

void 框架(TreeNode root) {
	//处理root
    框架(root.left);
    框架(root.right);
}

就本题让而言，分别判断两棵树的左子树和右子树是否相等，从两个树的根节点出发同步比较，结构上的判断如果节点都为空则true、如果只有一个为空另一个不为空则false；数值上的判断就是比较相同结构位置上的值。

public boolean isSameTree(TreeNode p, TreeNode q) {
    //结构上
    if (p==null&&q==null)return true;
    if (p==null||q==null)return false;
    //数值上不等则false，相等则继续判断其他节点的数值
    if (p.val!=q.val)return false;
    return isSameTree(p.left,q.left)&&
        isSameTree(p.right,q.right);
}

时间复杂度：O(n)

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github