二叉树的遍历
前序遍历：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
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 isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}else{
return false;
}
}
}
层次遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
Queue<TreeNode> s1 = new LinkedList<>();
Queue<TreeNode> s2 = new LinkedList<>();
if(p == null && q == null) return true;
if(p == null || q ==null) return false;
s1.add(p);s2.add(q);
while(!s1.isEmpty() && !s2.isEmpty()){
int size1 = s1.size();
for(int i=0;i<size1;i++){
TreeNode t1 = s1.poll();
TreeNode t2 = s2.poll();
if(t1.val != t2.val) return false;
//下面的if判断可以保证两个队列的大小一定相等否则就直接返回false了
if(t1.left != null && t2.left != null){
s1.add(t1.left);
s2.add(t2.left);
}
if(t1.right != null && t2.right != null){
s1.add(t1.right);
s2.add(t2.right);
}
if(t1.left != null ^ t2.left != null){//异或，当一个为null,一个不为null时为真
return false;
}
if(t1.right != null ^ t2.right != null){
return false;
}
}
}
return true;
}
}
两个解法时间复杂度都差不多
