azl397985856 commented 2 years ago

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

Richard-LYF commented 2 years ago

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: TreeNode, q: TreeNode) -> bool: if p and q: if p.val != q.val: return False else: return self.isSameTree(p.left,q.left) and self.isSameTree(q.right,p.right) if not p and not q: return True else: return False

yan0327 commented 2 years ago

思路：后续遍历DFS 判断p，q是否相等需要满足： 1.p,q 同时为nil 2.不存在p，q其中一个为nil的情况 3.不存在p.Val != q.Val 4.p和q的子树都满足这样的条件

类似的题目： 1.判断p，q是否对称树 =》区别在于遍历的时候是p.Left,q.Right && p.Right,p.Left

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

时间复杂度O（n）空间复杂度O（h）

BpointA commented 2 years ago

思路

递归

JAVA代码

/**
 * 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;
        }
        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));
        }

    }
}

zwmanman commented 2 years ago

思路

First check input node(recursion exist)
Check left subtree and right subtree

代码

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, q.left) and self.isSameTree(p.right, q.right)

复杂度分析

时间复杂度：O(N)，其中 N 为Node个数。
空间复杂度：O(1)

spacker-343 commented 2 years ago

思路

分为无孩子，有一个孩子，有两个孩子三种情况来设置递归终止条件。

代码

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;
        }
        // 为false了就不用往下递归了
        if(!isSameTree(p.left, q.left)){
            return false;
        }
        if(!isSameTree(p.right, q.right)){
            return false;
        }
        return true;
    }
}

复杂度

时间复杂度：O(n) 空间复杂度：O(h)

yetfan commented 2 years ago

思路边界 + 根 + 左子树 + 右子树

代码

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

复杂度 时间 O(n) 空间 O(n)

Grendelta commented 2 years ago

思路

递归

代码

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

复杂度

时间复杂度O(N)

空间复杂度O(N)

rzhao010 commented 2 years ago

Thought

Basic recursion

Code

    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);
    }

Complexity

Time: O(n)
Space: O(n)

Alexno1no2 commented 2 years ago

# 比较两个根节点：
# 当两节点都为空，相同，返回True；
# 当两节点只有一个为空，不同，返回False；
# 当两节点值不相同，不同，返回False
# 当两个节点值相同，则拿这两个节点的左子树相互比较、右子树相互比较，左右子树全部相同，最后结果才是相同

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p is None and q is None:
            return True
        elif p is None or 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)

wangzehan123 commented 2 years ago

代码

语言支持：Java

Java Code:


class Solution {
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);
    }
}

Tao-Mao commented 2 years ago

Idea

Recursion

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

Complexity

Space: O(logn) Time: O(n)

moirobinzhang commented 2 years ago

Idea: Recursion

Code: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if p is None and q is None: return True

    if p is None or q is None:
        return False

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

Complexity Space: O(n) Time: O(n)

feifan-bai commented 2 years ago

思路

判断几个特殊情况(子树全为空，其中有一个为空)

递归调用函数直至最底层(DFS) 代码

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(N), N = min(m, n), m, n 为p, q 节点数
空间复杂度：O(N), N = min(m, n)，m, n 为p, q 节点数

baddate commented 2 years ago

题目

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

思路

二者均为空，相同

只有一个为空，不同

都不为空，但是值不同，不同

递归左右子树

代码

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->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))，M和N分别为二者节点数

ninghuang456 commented 2 years ago

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; // why not  if(p.val == q.val) return true;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

    }
}

CoreJa commented 2 years ago

思路

递归：一行我秒了，有什么好说的 return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) if p and q else p == q

非递归：用两个队列维护，pop出来的如果p和q都不是None就比较，然后leftright继续入队；如果有一个none那就直接看p!=q

代码

class Solution:
# 递归：一行我秒了，有什么好说的
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
    return p.val == q.val \
           and self.isSameTree(p.left, q.left) \
           and self.isSameTree(p.right, q.right) \
        if p and q else p == q
# 非递归：用两个队列维护，pop出来的如果p和q都不是None就比较，然后leftright继续入队；
# 如果有一个none那就直接看p!=q
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
    queue_p = deque([p])
    queue_q = deque([q])

    while len(queue_p) and len(queue_q):
        p = queue_p.popleft()
        q = queue_q.popleft()
        if p and q:
            if p.val != q.val:
                return False
            queue_p.append(p.left)
            queue_p.append(p.right)
            queue_q.append(q.left)
            queue_q.append(q.right)
        else:
            if p != q:
                return False

    return len(queue_p) == len(queue_q)

laofuWF commented 2 years ago

    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)

zjsuper commented 2 years ago

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

YuhanJYH commented 2 years ago

recursion


class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {

        if(!p && !q)
        {
            return true;
        }
        else if(p && !q || !p && q || p->val != q->val )
        {
            return false;
        }

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

    }
};

Time: O(n); Space： O(n);

Husky-Gong commented 2 years ago

Solution

check whether the root is same
check their children -> left and right accordingly
return boolean

Code

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

        // only one is null
        if (p == null || q == null) {
            return false;
        }

        // if value is not same
        if (p.val != q.val) {
            return false;
        }

        // check children
        boolean left = isSameTree(p.left, q.left);

        boolean right = isSameTree(p.right, q.right);

        return left && right;
    }
}

Complexity

Time Complexity: O(N) Space Complexity: O(N)

zhy3213 commented 2 years ago

思路

一行递归但我是傻子

代码

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

qihang-dai commented 2 years ago

Time O(N) Space O(lN)

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

}

xj-yan commented 2 years ago

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

Time Complexity: O(n), Space Complexity: O(n)

CodeWithIris commented 2 years ago

Question

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

Note (DFS)

Compare the two nodes from the P tree and Q tree respectively. If they are both null pointers, return true(The previous nodes are the same). If one of the pointers is a null pointer, return false. If their values are different, return false.
Use deep first search to traverse the trees.

Solution (C++)


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

Complexity

T: O(min(m, n)): If they are the same tree, the time complexity is O(m) = O(n). If not, the time complexity is O(min(m,n)).
S: O(min(m, n)): The worst situation is that the nodes are equal to the depth of the tree.

ZacheryCao commented 2 years ago

Idea

DFS. Preorder scan both trees and compare current node's value whether are same. If not same return False, else continue to scan subtree till none. Return true only if both trees hit none.

Code:

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)

Complexity

Time: O(N) Space: O(N).

haixiaolu commented 2 years ago

思路： DFS

边界
- 比较两棵树都为空，返回True
- 只有一棵树为空，返回False
DFS
- 如果值不同，返回False
- 递归两棵树的左右子树

代码 / Python

 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
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

复杂度分析：

时间复杂度： O(n)
空间复杂度： O(h)

RocJeMaintiendrai commented 2 years ago

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);
    }
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(depth)

Toms-BigData commented 2 years ago

【Day 14】100. 相同的树

思路

同时遍历两棵树，情况不同返回false

golang代码

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

复杂度

时间：O(n) 空间:O(n)

tongxw commented 2 years ago

思路

先序DFS

代码

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 {
            return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}

SC: O(N) TC: O(logN)

caohaha commented 2 years ago

思路

递归实现， p q均为空节点，true p q一空一非空 false p q的值不相等 false 递归遍历p的左子树与q的左子树 p的右子树与q的右子树是否相同

C++实现

class Solution 
{
public:
    bool isSameTree(TreeNode* p, TreeNode* q) 
    {
        // base case
        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);
    }
};

复杂度分析

时间复杂度O(n)
空间复杂度O(n)

ZhangNN2018 commented 2 years ago

思路

递归
左右子树分别递归
注意边界条件

复杂度

时间复杂度: O(N) ,N为两棵树的最小节点数；
空间复杂度: O(N)。

代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not p and not q: #同时为空，true
            return True
        if not p or not q: #有一个先空了，false
            return False
        if p.val != q.val: #都没空，但值不等，false
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right,q.right)

Yachen-Guo commented 2 years ago

思路

recursion, 有着相同的根节点&相同的左子树&相同的右子树 =》树是相同的

notes: 必须前序&中序，中序&后序，两种遍历方式都得到相同的数组，才能确定两树相同

代码

/**
 * 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);
    }
}

hdyhdy commented 2 years ago

思路：采用深度优先遍历，设置条件当两个节点val不同，或者一个节点存在另外一个节点不存在的时候输出false等条件判断。

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

时间空间复杂度都为min（n,m）

L-SUI commented 2 years ago

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

ggohem commented 2 years ago

思路：

可以通过搜索的方式判断两个二叉树是否相同。

于是，有两种遍历方法：

DFS(先对根结点进行逻辑处理，然后递归与他邻接的点)：
- 两个根结点都为空，相同；一空一不空，不同；
- 两个根结点都不空，但是二者的值不相等，不同；
- 递归两个根节点的左结点和右结点；
BFS(根结点不空则入队，队不空时循环，出队结点，对出队结点的邻接点进行逻辑处理，满足条件的入队)：
- 两个根结点都为空，相同；一空一不空，不同；
- 两个根结点不空时，分别入队；
- 两个队不空时，循环：
- 出队，两个结点值不相等，不同；两个结点的左/右结点一空一不空，不同；
- 当左/右结点不空时，入队，要注意左/右结点的入队顺序要一致，先入左结点，再入右结点，左右结点的值留在出队的时候再判断；

代码：

DFS:

/**
* 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);
  }
}

BFS：

import java.util.LinkedList;
import java.util.Queue;

/**
* 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;
      Queue<TreeNode> queue1 = new LinkedList<>();
      Queue<TreeNode> queue2 = new LinkedList<>();
      queue1.offer(p);
      queue2.offer(q);
      while (!queue1.isEmpty() && !queue2.isEmpty()) {
          TreeNode node1 = queue1.poll(), node2 = queue2.poll();
          if (node1.val != node2.val) return false;
          TreeNode left1 = node1.left, right1 = node1.right;
          TreeNode left2 = node2.left, right2 = node2.right;
          // ^ 异或符，相同为0，不同为1
          if (left1 == null ^ left2 == null) return false;
          if (right1 == null ^ right2 == null) return false;
          if (left1!=null&&left2!=null){
              queue1.offer(left1);
              queue2.offer(left2);
          }
          if (right1!=null&&right2!=null){
              queue1.offer(right1);
              queue2.offer(right2);
          }
      }
      return queue1.isEmpty()&&queue2.isEmpty();
  }
}

时空复杂度：

时间复杂度：
- DFS：O(min(m,n))
- BFS：O(min(m,n))
- m和n分别时两个二叉树的结点数，访问的结点数不会超过较少的二叉树结点数。
空间复杂度：
- DFS：O(min(m,n))，DFS的空间复杂度取决于递归调用层数(二叉树高度)，最坏情况下，二叉树的高度等于结点数。
- BFS：O(min(m,n))，BFS的空间复杂度取决于队列里的结点个数，队列结点数不会超过较少的二叉树结点数。

GaoMinghao commented 2 years ago

思路

利用BFS的方法，一边遍历一边判断，代码很长，不过执行速度是很可观的，因为可以很快终止不一致的场景

代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if((p!=null)^(q!=null)) {
            return false;
        }
        if(p == null) {
            return true;
        }
        if( p.val != q.val) {
            return false;
        }
        List<TreeNode> QueueP = new ArrayList<>();
        QueueP.add(p);
        List<TreeNode> QueueQ = new ArrayList<>();
        QueueQ.add(q);
        while((!QueueP.isEmpty()) && (!QueueQ.isEmpty())) {
            TreeNode AL = QueueP.get(0).left;
            TreeNode BL = QueueQ.get(0).left;
            if((AL!=null)^(BL!=null)) {
                return false;
            } else if(AL != null) {
                if(AL.val != BL.val) {
                    return false;
                } else {
                    QueueP.add(AL);
                    QueueQ.add(BL);
                }
            }
            TreeNode AR = QueueP.get(0).right;
            TreeNode BR = QueueQ.get(0).right;
            if((AR!=null)^(BR!=null)) {
                return false;
            } else if(AR != null) {
                if(AR.val != BR.val) {
                    return false;
                } else {
                    QueueP.add(AR);
                    QueueQ.add(BR);
                }
            }
            QueueP.remove(0);
            QueueQ.remove(0);
        }
        return true;
    }
}

复杂度

时间复杂度O(min(p,q)) 空间复杂度O(min(p,q))

mannnn6 commented 2 years ago

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);
        }
    }
}

KennethAlgol commented 2 years ago

思路

使用Queue

语言

JAVA

/**
 * 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;
        }
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue1.offer(p);
        queue2.offer(q);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if (node1.val != node2.val) {
                return false;
            }
            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
            if (left1 == null ^ left2 == null) {
                return false;
            }
            if (right1 == null ^ right2 == null) {
                return false;
            }
            if (left1 != null) {
                queue1.offer(left1);
            }
            if (right1 != null) {
                queue1.offer(right1);
            }
            if (left2 != null) {
                queue2.offer(left2);
            }
            if (right2 != null) {
                queue2.offer(right2);
            }
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

复杂度分析

时间复杂度 O(n) 空间复杂度 O(n)

SenDSproject commented 2 years ago

解题思路：分治，我们先去看看树的右边，再去看看树的左边，如果两边都是一样的而且根的value 也是一样的，那么这两颗就是一样的树



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

        outside = self.isSameTree(p.left, q.left)
        inside = self.isSameTree(p.right, q.right)
        isSame = outside and inside

        return isSame

Time Complexity : O(N)
Space Complexity : O(N)

yuetong3yu commented 2 years ago

100. 相同的树

如果用递归解决这个问题的话，我们套用递归的模板：

递归遇到的最小情况，也即是递归的出口。
递归的本质就是将大问题分解成小问题进行求解，递归不断的减小才能收敛到递归出口。
递归调用的父问题和子问题之间没有交集（不然会无限递归）。

var isSameTree = (p, q) => {
  // recursion outa
  if (!q || !p) {
    return !q && !p
  }
  return (
    p.val === q.val &&
    isSameTree(p.left, q.left) &&
    isSameTree(p.right, q.right)
  )
}

callmeerika commented 2 years ago

思路

利用递归

代码

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)

charlestang commented 2 years ago

思路

递归

边界：如果两个树都为空，则返回 True，如果其中一棵树为空，返回False

代码

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)

时间复杂度 O(n)

pengfeichencpf commented 2 years ago

class Solution { 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); } }

gentleman-goodman commented 2 years ago

Day_14_100_相同的树.md

思路



一开始就想到dfs写法，判断情况就是当头节点都是空的情况，就直接true了
否则看看左右子节点，左右子节点就分两种情况，if都是不为空，就判断是不是相同
即要求p != null && q != null && p.val == q.val（注意并且val ==val）
如果都为空，就是直接true，
其他情况，比如一个空，一个不空，说明不相同，直接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) {
            if (p == null && q == null) {
                return true;
            }
            if (p != null && q != null && p.val == q.val) {
                return isSameTree(p.right, q.right) && isSameTree(p.left, q.left);

            }
            return false;

        }
    }

复杂度分析

LannyX commented 2 years ago

思路

递归

代码

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);
    }
}

复杂度分析

时间复杂度：O(N)
空间复杂度：O(h), h为树的高度

biscuit279 commented 2 years ago

思路：

递归判断，若值不相等或结构不相等，返回false

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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, q.left) and self.isSameTree(p.right, q.right)

时间复杂度：O（N）空间复杂度：O（H）

taojin1992 commented 2 years ago

pre-order, compare root first, empty check and then val check, recursively compare the subtrees

Time: O(n). n=number of nodes
Space: O(height)

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

testeducative commented 2 years ago

思路

递归判断

代码


/**
 * 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 == 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);
    }
};

tangjy149 commented 2 years ago

思路

递归判断左子树和右子树

代码

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

复杂度

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

Menglin-l commented 2 years ago

approach1: recursion

code

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

        boolean left = isSameTree(p.left, q.left);
        boolean right = isSameTree(p.right, q.right);

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

        return left && right;
    }
}

approach2: iteration

code

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

        Queue<TreeNode> que = new LinkedList<>();
        que.offer(p);
        que.offer(q);

        while (!que.isEmpty()) {

            TreeNode currP = que.poll();
            TreeNode currQ = que.poll();

            if (currP == null && currQ == null) continue;
            if (currP == null || currQ == null || currP.val != currQ.val) return false;

            que.offer(currP.left);
            que.offer(currQ.left);

            que.offer(currP.right);
            que.offer(currQ.right);

        }
        return true;
    }
}

leetcode-pp / 91alg-6-daily-check

【Day 14 】2021-12-25 - 100. 相同的树 #21

100. 相同的树

入选理由

题目地址

前置知识

题目描述

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

思路

JAVA代码

思路

代码

思路

代码

复杂度

思路

代码

复杂度

代码

Idea

Code

Complexity

题目

思路

代码

思路

代码

Solution

Code

Complexity

思路

代码

Question

Note (DFS)

Solution (C++)

Idea

Code:

Complexity

思路： DFS

代码 / Python

复杂度分析：

【Day 14】100. 相同的树

思路

golang代码

复杂度

思路

代码

思路

C++实现

复杂度分析

思路

复杂度

代码

思路

代码

思路：

代码：

时空复杂度：

思路

代码

复杂度

思路

语言

复杂度分析

思路

代码

复杂度

思路

代码

思路

思路

代码

思路：

思路

代码