首页 > 代码库 > 学习笔记：LeetCode176：
学习笔记：LeetCode176：
LeetCode176：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.
判断两个二叉树是否相等，判断依据：结构相同，节点值相等
树节点包含当前值及分别指向其左右子节点的引用，如下：
1 /**2 * Definition for binary tree3 * public class TreeNode {4 * int val;5 * TreeNode left;6 * TreeNode right;7 * TreeNode(int x) { val = x; }8 * }9 */
考虑问题，对于当前树A和树B而言，两个树结构相同且每个节点都相等时才可以说A == B
于是有A_Root = B_Root，A_LeftTree = B_leftTree，A_rightTree = B_rightTree
这样问题就可以采用分治递归的来解决：
问题可以转化为：
当前节点相等，当前节点左右子树也都相等 ——> 两个树相等
逐层下推直到两个树同时不再有子节点为止。
递归返回条件：
A_Root，B_Root 均不存在时，表示结构一致，返回true
A_Root = B_Root有一个存在时，表示结构不一致，返回false
A_Root，B_Root 都存在时，结构一致，判断值是否相等，否则返回false
完整代码如下：
1 public class Solution { 2 public boolean isSameTree(TreeNode p, TreeNode q) { 3 if (p == null && q == null){ 4 return true; 5 } 6 if (p == null && q != null){ 7 return false; 8 } 9 if (p != null && q == null){10 return false;11 } 12 if (p.val != q.val){13 return false;14 } 15 return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);16 }17 }
我是华丽丽的分割线
补充：
1、首先本题没考虑左右子树置换的问题，因此不需要进行二次判断
如果考虑该问题，那么二次判断的递归如下：
isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
2、本题所采用的方法实质上就是二叉树的先序遍历过程，时间复杂度O(n)，空间复杂度O(logn)
学习笔记：LeetCode176：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。