LeetCode100：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)