【Day 14 】2022-11-14 - 100. 相同的树

[azl397985856]

100. 相同的树

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/same-tree/

前置知识

• 递归
• 层序遍历
• 前中序确定一棵树

  题目描述

  
  给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入: 1 1 / \ / \ 2 3 2 3

    [1,2,3],   [1,2,3]

输出: true 示例 2:

输入: 1 1 / \ 2 2

    [1,2],     [1,null,2]

输出: false 示例 3:

输入: 1 1 / \ / \ 2 1 1 2

    [1,2,1],   [1,1,2]

输出: false

[whoam-challenge]

思路

迭代

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        elif p is None and q is not None:
            return False
        elif p is not None and q is None:
            return False
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

复杂度分析

-时间复杂度分析： O(\min(m,n))O(min(m,n))，其中 mm 和 nn 分别是两个二叉树的节点数

-空间复杂度分析 O(\min(m,n))O(min(m,n))

[zhiyuanpeng]

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:

        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        elif p and not q:
            return False
        elif not p and q:
            return False
        else:
            return True

time O(N) space O(logN)

[tiandao043]

思路

dfs 挨个比，出口俩空true，只有一个空false，值不同false，否则递归左右子树。

代码

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {       
        if(p==nullptr && q==nullptr){
            return true;
        }else if(p==nullptr || q==nullptr){
            return false;
        }else if(p->val==q->val){
            bool a=isSameTree(p->left,q->left);
            bool b=isSameTree(p->right,q->right);
            return a&&b;
        }else{
            return false;
        }         
    }
};

or

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q) return true;
        if(!p || !q) return false;
        if((p->val == q->val) && isSameTree(p->left,q->left) && isSameTree(p->right,q->right))
        return true;
        else{
            return false;
        }       
    }
};

O(n)

思路

看了官方题解 bfs 其中可以使用异或，表示两者不同的情况，也就是一个null一个有值，也可以考虑使用非指针的与和或来表示只有一个不为空的情况。 if (!leftNode && !rightNode) { // continue; }
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) { return false; }

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        } else if (p == nullptr || q == nullptr) {
            return false;
        }
        queue <TreeNode*> queue1, queue2;
        queue1.push(p);
        queue2.push(q);
        while (!queue1.empty() && !queue2.empty()) {
            auto node1 = queue1.front();
            queue1.pop();
            auto node2 = queue2.front();
            queue2.pop();
            if (node1->val != node2->val) {
                return false;
            }
            auto left1 = node1->left, right1 = node1->right, left2 = node2->left, right2 = node2->right;
            if ((left1 == nullptr) ^ (left2 == nullptr)) {
                return false;
            }
            if ((right1 == nullptr) ^ (right2 == nullptr)) {
                return false;
            }
            if (left1 != nullptr) {
                queue1.push(left1);
            }
            if (right1 != nullptr) {
                queue1.push(right1);
            }
            if (left2 != nullptr) {
                queue2.push(left2);
            }
            if (right2 != nullptr) {
                queue2.push(right2);
            }
        }
        return queue1.empty() && queue2.empty();
    }
};

or

class Solution {
public:

    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) return true;
        if (p == NULL || q == NULL) return false;
        queue<TreeNode*> que;
        que.push(p);   //
        que.push(q);  //
        while (!que.empty()) {  //
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  //
                continue;
            }
            //
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   //
            que.push(rightNode->left); //
            que.push(leftNode->right);  //
            que.push(rightNode->right);  //
        }
        return true;
    }
};

[y4h2]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False

        if p.val != q.val:
            return False

        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

[bwspsu]

(参考题解学习)

思路： 迭代

代码：

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

复杂度：

TC: O(n) SC: O(h)

[Abby-xu]

思路

BFS or recursion

代码

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # BFS
        # queue = [(p, q)]
        # while queue:
        #     node1, node2 = queue.pop(0)
        #     if not node1 and not node2: # no child
        #         continue
        #     elif None in [node1, node2]:
        #         return False
        #     else:
        #         if node1.val != node2.val:
        #             return False
        #         queue.append((node1.left, node2.left))
        #         queue.append((node1.right, node2.right))
        # return True

        #DFS
        if not p and not q: return True
        if not p or not q: return False
        return p.val == q.val and self.isSameTree(q.left, p.left) and self.isSameTree(q.right, p.right)

复杂度

O(n)

[chenming-cao]

解题思路

递归，每个节点分别判断节点是否都为空，是否节点值相等，两个左子树是否相等，两个右子树是否分别相等。

代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        else if (p == null || q == null) return false;
        else if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

复杂度分析

• 时间复杂度：O(n)，n为树的节点数
• 空间复杂度：O(h)，h为树的高度

[zjsuper]

class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if not p and not q: return True elif not p or not q: return False if p.val != q.val: return False return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

[testplm]

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not p and not q:
            return True
        if not p or not q:
            return False
        return p.val==q.val and self.isSameTree(p.left,p.left) and self.isSameTree(q.right,q.right)

• Time:O(N)，其中 N 为树的节点数。
• Space: O(h)，其中 h 为树的高度。

[JancerWu]

思路

递归

代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) return p == q;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

复杂度

• 时间：O(n)
• 空间：O(h)

[ringo1597]

思路

方法：深度优先搜索 如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。

代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        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);
        }
    }
}

[yin02]

思路

如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。

代码

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        elif not p or not q:
            return False
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

复杂度分析

• 时间复杂度：O(min(m,n))
• 空间复杂度：O(min(m,n))

[ceramickitten]

思路

分治，根节点相等，且左右子树相等

代码

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is None and q is None
        return p.val == q.val \
               and self.isSameTree(p.left, q.left) \
               and self.isSameTree(p.right, q.right)

复杂度分析

n = min(p.size, q.size)

• Time: O(n) 遍历每个节点
• Space: O(n) 树的高度

[mayloveless]

思路

dfs ，递归比较，结束条件：都为空是相等，一个为空不相等，都不为空值不同为不想等。

代码

var isSameTree = function(p, q) {
    if (!q && !p) return true;
    if (!q || !p) return false;
    if (q.val !== p.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

复杂度

时间：O(min(n,m)) 遍历 空间：O(min(m,n)) 递归栈空间最差是节点数

[Whisht]

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:  # 二者均为空
            return True
        if (not p and q) or (p and not q):  # 一个为空，另一个非空
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

[MDGE]

var isSameTree = function(p, q) { if(!p && !q){ return true } if(p && q && p.val === q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right)){ return true } return false };

[954545647]

思路

1. 递归
2. 前序和中序遍历结果可以确定一颗树

代码

 var isSameTree = function(p, q) {
    if(p === null && q === null) return true;
  if(p && !q) return false;
  if(!p && q) return false;
  return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right , q.right)
};

// 前序&&中序

var isSameTree = function(p, q) {
  const preOrderP = preOrder(p,[])
  const preOrderQ = preOrder(q,[])
  const middleOrderP = middleOrder(p,[])
  const middleOrderQ = middleOrder(q,[])
  return preOrderP.join(" ") === preOrderQ.join(" ") && middleOrderP.join(" ") === middleOrderQ.join(" ") 
};

function preOrder(root,arr){
  if(root === null){
    arr.push(" ")
    return arr
  }
  arr.push(root.val);
  preOrder(root.left, arr);
  preOrder(root.right, arr);
  return arr
}

function middleOrder(root,arr){
  if(root === null){
    arr.push(" ")
    return arr
  }
  preOrder(root.left, arr);
  arr.push(root.val);
  preOrder(root.right, arr);
  return arr
}

空间复杂度

• 时间复杂度：O(N)，其中 N 为树的节点数。

• 空间复杂度：O(h)，其中 h 为树的高度。

[snmyj]

class Solution{
public boolean isSameTree(TreeNode p, TreeNode q) {
    return inorderTraversal(p,q);
}
private boolean inorderTraversal(TreeNode p, TreeNode q) {
    if(p==null&&q==null){
        return true;
    }else if(p==null || q==null){
        return false;
    }

    if(!inorderTraversal(p.left,q.left)){
        return false;
    }

    if(p.val!=q.val){
       return false;
    }

    if(!inorderTraversal(p.right,q.right)){
        return false;
    }
    return true;
}
}

[Frederickfan]

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        elif p is None and q is not None:
            return False
        elif p is not None and q is None:
            return False
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

[zhuzhu096]

先检查当前根节点，再检查当前节点的左右节点； 然后递归，将左右节点作为根节点，继续检查左右 class Solution { public: bool isSameTree(TreeNode p, TreeNode q) { if(p == nullptr && q == nullptr) return true; if( p == nullptr && q != nullptr) return false; if(p != nullptr && q == nullptr) return false; return p->val==q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right); } };

[xiaomingshixiaotang]

思路

1. 判断两棵子树是否相同的行为是一样的，我们考虑使用递归的方式求解两棵树是否相同
2. 当两棵树的根节点都为NULL时，返回true；当只有一棵树的根节点为NULL时，返回false；当两棵树的根节点都不为NULL，但当前节点的值不同时返回false；当两颗树的根几点都不为NULL,且当前节点的值相同时，判断这两棵树的左子树和右子树是否都相同

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q)
        {
            return true;
        }
        if((p && !q) || (!p && q))
        {
            return false;
        }
        if((p && q) && (p->val != q->val))
        {
            return false;
        }
        if((p && q) && (p->val == q->val))
        {
             return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
        }

        return false;
    }
};

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(n)

[sclihuiming]

思路

先判断一个节点是否相等， 然后递归调用

代码

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    } else if p == nil || q == nil {
        return false
    }
    if p.Val != q.Val {
        return false
    }
    a := isSameTree(p.Left, q.Left)
    b := isSameTree(p.Right, q.Right)
    return a && b
}

[FlipN9]

/**
 *  Preorder  TC:O(n), SC:O(h)
 * /
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null)
            return p == q;
        if (p.val != q.val)
            return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

[Alyenor]

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if(!p&&!q) return true
    if ((p&&!q) || (q&&!p) || (p.val!==q.val)) return false
    return isSameTree(p.left,q.left) &&isSameTree(p.right,q.right)
};

[yuexi001]

思路

对两棵树同时做先序遍历，对每个p、q进行判断，当p、p均为空时，返回true；当p或者q有个一个为空时，返回false；当p->val != q->val时，返回false；当p->val == q->val时，对其左右结点重复上述过程。

代码

C++ Code:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return preorder(p, q);
    }

    bool preorder(TreeNode* p, TreeNode* q){
        if(p == nullptr && q == nullptr)
            return true;
        if(!p)
            return false;
        if(!q)
            return false;

        if(p->val != q->val)
            return false;
        else{
            bool l = preorder(p->left, q->left);
            bool r = preorder(p->right, q->right);
            return l && r;
        }        
    }
};

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

[paopaohua]

思路

递归

代码

/**
* 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;
}else if(p == null || q == null){
return false;
}
if(q.val != p.val){
return false;
}
return isSameTree(q.left,p.left) && isSameTree(p.right,q.right);

}

}

### 复杂度
- 时间：o(n)
- 空间：o(n)   n为树的高度

[GG925407590]

思路 递归

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        if (p == nullptr || q == nullptr || p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

复杂度 时间：o(n) 空间：o(n) n为树的高度

[Elsa-zhang]

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSameTree(self , p: TreeNode, q:TreeNode):
        if not p and not q:
            return True
        if not p or not q:
            return False
        return p.val==q.val and \
            (self.isSameTree(p.left, q.left)) and \
                (self.isSameTree(p.right, q.right))

[yoco323]

思路

递归

/**
 * 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 false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

[MaylingLin]

思路

深度优先搜索，递归的判断是否相同

代码

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        elif not p or not q:
            return False
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

复杂度

• Time: $O(min(m,n))$, m和n分别为两个二叉树的节点数
• Space: $O(min(m,n))$, m和n分别为两个二叉树的节点数

[hxj2001]

思路

递归

代码

class Solution {  
public:  
   bool background(TreeNode* left, TreeNode* right) {  
       if (left == NULL && right != NULL) return false;  
       else if (left != NULL && right == NULL) return false;  
       else if (left == NULL && right == NULL) return true;  
       else if (left->val != right->val) return false;  
       else return background(left->left, right->left) && background(left->right, right->right);  

   }  
   bool isSameTree(TreeNode* p, TreeNode* q) {  
       return background(p, q);  
   }  
 };  

复杂度

• 时间复杂度：O(min(m,n))
• 空间复杂度：O(min(m,n))

[zywang0]

Code

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        else if (p == null || q == null) return false;
        else if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

[klspta]

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if(p == null ^ q == null){
            return false;
        }
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

[buer1121]

class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:

思路：两个树按同一遍历顺序遍历，然后比较节点值，或者结构

    if not p and not q:
        return True
    elif not p or not q:
        return False
    elif p.val!=q.val:
        return False

    return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

[AstrKing]

思路

递归，拆分

代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        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);
        }
    }
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[Dark-volute]

思路

比较两棵树的结构，可以对两棵树同时进行层级遍历，在遍历中比较节点，如果有不同的节点就提前退出。

需要注意的是遍历过程中空节点也要入列。

代码

JavaScript Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
    const queueP = [p];
    const queueQ = [q];

    while (queueP.length && queueQ.length) {
        let lenP = queueP.length;
        let lenQ = queueQ.length;

        // 如果两棵树同一层的节点数都不同，肯定不是同一棵树
        if (lenP !== lenQ) return false;

        while (lenP-- && lenQ--) {
            const nodeP = queueP.shift();
            const nodeQ = queueQ.shift();

            // 两个节点都是 null, 直接继续比较下一个节点
            if (!nodeP && !nodeQ) continue;
            // 遇到不同的节点，说明不是同一棵树，提前返回
            if (!nodeP || !nodeQ || nodeP.val !== nodeQ.val) return false;

            // 将下一层的节点入列，空节点也要入列
            queueP.push(nodeP.left, nodeP.right);
            queueQ.push(nodeQ.left, nodeQ.right);
        }
    }
    return true;
};

复杂度分析

时间复杂度：$O(N)$，N 为二叉树的节点数。 空间复杂度：$O(logN)$，N 为二叉树的节点数。

[bookyue]

code

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;

        if (q.val != p.val) return false;

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

[wtdcai]

代码

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        #1
        if p is None and q is None:
            return True
        elif p is None or q is None:
            return False
        else:
            if p.val ==q.val:
                leftsame = self.isSameTree(p.left,q.left)
                rightsame = self.isSameTree(p.right,q.right)
                if leftsame and rightsame:
                    return True
                else:
                    return False
            else:
                return False

复杂度分析

O(min(m,n))
O(min(m,n))

[ghost]

代码

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True 
        if not p or not q or p.val != q.val:
            return False

        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

[richypang]

public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; if (p == null || q == null) return false;

    if (q.val != p.val) return false;

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

[RestlessBreeze]

代码

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        } else if (p == nullptr || q == nullptr) {
            return false;
        } else if (p->val != q->val) {
            return false;
        } else {
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
    }
};

[tzuikuo]

思路

递归，判断左右子树是否都相同。相同：分类讨论

代码

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p&&!q) return true;
        if(!p&&q||!q&&p) return false;
        if(p->val!=q->val) return false;
        return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[Jetery]

100. 相同的树

思路

DFS

代码 (cpp)

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        else if (p == nullptr || q == nullptr) return false;
        else if (p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

复杂度分析

• 时间复杂度：O(min(m,n)) (m, n为树的节点数)
• 空间复杂度：O(min(m,n))

[AtaraxyAdong]

思路

层序遍历，递归比较每层的节点是否相等

代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {

        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }

        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

复杂度分析

• 时间复杂度：O(min(M,N))（M、N分别是两棵树的高度）
• 空间复杂度：O(min(M,N))

[A-PolarBear]

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==nullptr && q==nullptr) return true;
        if(p==nullptr && q!=nullptr) return false;
        if(p!=nullptr && q==nullptr) return false;

        return (p->val==q->val) && isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
};

[A-pricity]

/**

• 解题思路：
• 深度优先遍历
• 结束条件：当两棵树的当前节点都为空，return true
• 当其中一个是null 另一个不为null,return false
• 两个都不为空，且其值不相等，return false
• 当满足终止条件时进行返回，不满足时分别判断左子树和右子树是否相同，其中要注意代码中的短路效应 */ /**
• Definition for a binary tree node.
• function TreeNode(val, left, right) {
• this.val = (val===undefined ? 0 : val)
• this.left = (left===undefined ? null : left)
• this.right = (right===undefined ? null : right)
• } */ /**
• @param {TreeNode} p
• @param {TreeNode} q
• @return {boolean} */ var isSameTree = function(p, q) { if(q == null && p == null) return true; if(p == null || q == null) return false; if(p.val != q.val) return false; return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right); };

[xuanaxuan]

思路

判断两棵树是否相同，只需要判断树相同位置的元素值是否相同。可以借助队列实现层次遍历，每次拿到两个节点时比较，注意当两个节点都为null时不能返回true( 因为还不一定),只能暂停这次循环，进行下一次。 如果不一致，直接返回 false。如果访问完都没有发现不一致就返回 true。

代码

function isSameTree(p, q) {
  let queueA = [];
  queueA.push(p);
  queueA.push(q);
  while (queueA.length) {
    const p = queueA.shift(),
      q = queueA.shift();
    if (p == null && q == null) {
      continue;
    }
    if (p == null || q == null || p.val != q.val) {
      return false;
    }
    queueA.push(p.left);
    queueA.push(q.left);

    queueA.push(p.right);
    queueA.push(q.right);
  }
  return true;
}

复杂度

时间复杂度：O(N)，其中 N 为树的节点数。 空间复杂度：O(Q)，其中 Q 为队列的长度最大值，在这里不会超过相邻两层的节点数的最大值。

[huibinny]

递归实现

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p == None and q == None:
            return True
        if p == None or q == None:
            return False
        if p.val != q.val:
            return False

        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

[SJ941127]

思路

深度遍历 终止条件

1. 两个都是null true
2. 其中一个为null false
3. 相同位置值不相等 false

代码

var isSameTree = function(p, q) {
    if(p===null && q===null) {
        return true
    }
    if(p===null || q===null) {
        return false
    }
    if(p.val !== q.val ) {
        return false
    }

    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right)
};

[liuajingliu]

解题思路

DFS

代码实现

javaScript

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
  if(!p && !q) return true
  if(!p || !q) return false;
  if(p.val != q.val) return false;

  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

复杂度分析

• 时间复杂度 $O(N)$
• 空间复杂度 $O(N)$