【Day 14 】2023-02-27 - 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

[JiangyanLiNEU]

• recursion
• T = O(N) N = number of nodes
• S = O(N) N = height of the tree

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

[zzhilin]

思路

recursively check every node in the two trees. base case: both nodes are none (True)

代码

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

复杂度分析 Time: O(N), number of nodes Space: O(N), number of nodes in recursion stack for an unbalanced tree

[Yufanzh]

# 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:
        # recursive way, get the base case first
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)        

[Leonalhq]

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

        # if p.val == q.val:
        #     return True
        left = self.isSameTree(p.left, q.left)
        right = self.isSameTree(p.right, q.right)

        return p.val == q.val and left and right

[Zoeyzyzyzy]

package Tree;

import java.util.LinkedList;

/* Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

*/

// Definition for a binary tree node.
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 {
    // think of that with preoder trversal, first compare current node, then compare
    // left & right.
    // only current.val & left & right are all same , the tree could be same

    // Recursive method:
    // Time Complexity: O(min(m,n)) - need to compare each node and stop when arrive
    // less total number,
    // Space Complexity: O(min(m,n)) - recursion space depends on tree height, worst
    // case tree's height equals to nodes.
    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);
    }

    // Iterative method:
    // Time Complexity: O(min(m+n)); Space Complexity: O(min(m,n));
    public boolean isSameTree1(TreeNode p, TreeNode q) {
        if (p == null && q == null)
            return true;
        if (p == null || q == null)
            return false;
        LinkedList<TreeNode> queue1 = new LinkedList<>();
        LinkedList<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(p);
        queue2.offer(q);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode cur1 = queue1.poll();
            TreeNode cur2 = queue2.poll();
            if (cur1.val != cur2.val)
                return false;
            TreeNode left1 = cur1.left, right1 = cur1.right,
                    left2 = cur2.left, right2 = cur2.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();
    }
}

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

[NorthSeacoder]

DFS

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

• TC:O(min(m,n))
• SC:O(min(m,n))

BFS

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    const queue = [p, q];
    while (queue.length) {
        const curP = queue.shift();
        const curQ = queue.shift();
        //不执行下一步但继续循环
        if (!curP && !curQ) continue;

        if (!curP || !curQ || curP.val !== curQ.val) return false;

        queue.push(curP.left)
        queue.push(curQ.left)

        queue.push(curP.right)
        queue.push(curQ.right)
    }
    return true;
};

• TC:O(min(m,n))
• SC:O(min(m,n))

[LIMBO42]

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

[yingchehu]

思路

兩個樹同時 dfs 一一檢查每個 node 是否一樣

Code

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

複查度

Time: O(N) Space: O(h)

[954545647]

思路

递归求解，注意边界条件

代码

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

复杂度分析 N 都为树节点的个数

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

[bookyue]

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

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

[airwalkers]

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

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

        return false;
    }
}

[csthaha]

复杂度：

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

代码：

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

[Elsa-zhang]

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

[Ryanbaiyansong]

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

[Meisgithub]

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

[huizsh]

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if (p == nil && q == nil) {
        return true
    }
    if (p == nil && q != nil) {
        return false
    }
    if (p != nil && q == nil) {
        return false
    }
    return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

[Abby-xu]

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)

[Quieter2018]

思路 递归；

代码

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if( p == NULL && q == NULL)  return true; //都为空
        if( p == NULL) return false; //一个为空，一个不为空
        if( q == NULL) return false;
        if( q->val != p->val) return false; //值不相等

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

    }
};

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

[Fuku-L]

思路

使用DFS或者BFS遍历二叉树，如果节点val相同，则继续遍历树的左子树或右子树。

代码

1. DFS遍历，使用递归方式，不断比较根节点的左子树和右子树的情况，如果其中一个节点非空，返回二者比较情况，如果两个节点非空，比较其值情况。空间复杂度低。

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

2. BFS遍历。使用一个队列（LinkedList）同时保存两个树当前的节点，循环队列直到队列为空，每次比较使，取出两个节点进行比较。

   /**
   class Solution {
   public boolean isSameTree(TreeNode p, TreeNode q) {
       // BFS 先进先出 -- 使用队列
       Queue<TreeNode> queue = new LinkedList<>();
       queue.add(p);
       queue.add(q);
       while (!queue.isEmpty()) {
           p = queue.poll();
           q = queue.poll();
           if (p == null && q == null){
               continue;
           }
   
           if ((p == null || q == null) || p.val != q.val) {
               return false;
           }
           queue.add(p.left);
           queue.add(q.left);
           queue.add(p.right);
           queue.add(q.right);
       }
       return true;
   }
   }

   复杂度分析

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

[chocolate-emperor]

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

[kofzhang]

思路

递归比较所有节点 如果两个节点都是None，返回True。如果一个是None，返回False。 如果两个节点值相等，则分别比较左右节点。

复杂度

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

代码

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

[chocolate-emperor]

class Solution {
public:
    queue<TreeNode*>q;
    int maxDepth(TreeNode* root) {
        if(root==nullptr)   return 0;
        else    q.push(root);
        int cnt = 0;
        while(!q.empty()){
            cnt +=1;
            int l = q.size();
            for(int i=0;i<l;i++){
                TreeNode* tmp = q.front();
                q.pop();

                if(tmp->left)   q.push(tmp->left);
                if(tmp->right)  q.push(tmp->right);
            }
        }
        return cnt;
    }
};

[sye9286]

思路

当pq都是null时，树是一样的。 只有一个null或值不相同，则树不同。 值相同时，递归遍历比较子树。只有左右子树都一样树才一样，否则只要有一个false就返回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)
};

[hshen202108]

题目地址(100. 相同的树)

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

题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

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

 

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

 

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104

前置知识

递归

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

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

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$，其中n为树的节点个数
• 空间复杂度：$O(h)$，其中h为树的深度

[Bochengwan]

思路

DFS或bfs，随时deep的迭代，比较是否为相同的结构。

代码

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(min(m,n）)，其中 m和n为两棵树的节点数
• 空间复杂度：O(min(m,n）)，其中 m和n为两棵树的节点数

[jmaStella]

思路

base case：q和p都为null， true。 q和p中只有一个为null，false。q值和p值不想等，false。 recursive：q.left p.left && q.right p.right

代码

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

复杂度

时间：O(N) 每一个node都要到 空间：O（N）

[wangzh0114]

思路

• 递归

  代码

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

  ---

  复杂度分析

• TC:O(N)
• SC:O(N)

[harperz24]

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

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

        # dfs
        # time: O(n)
        # space: O(n)

[luckyoneday]

代码

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

[AstrKing]

思路

依次比较两颗树的子节点

代码

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(min(m,n）)，其中 m和n为两棵树的节点数

空间复杂度：O(min(m,n）)，其中 m和n为两棵树的节点数

[Hughlin07]

class Solution {

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

}

Time: O(N) Space: O(h)

[X1AOX1A]

0100. 相同的树

题目

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

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

思路

• 同时对两棵树进行 DFS，并比较节点值，若不相同则 False，相同则继续 DFS

代码

# 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:

        # DFS 
        def is_same_node(node1, node2):
            # 1. 都为 None，返回 True
            if not node1 and not node2:
                return True
            # 2. 都不为 None
            elif node1 and node2:
                # 2.1 值不相同，返回 Flase
                if node1.val != node2.val:
                    return False
                # 2.2 值相同，继续 DFS
                else:
                    if not is_same_node(node1.left, node2.left) or not is_same_node(node1.right, node2.right):
                        return False
                    else:
                        return True
            # 3. 一个为 None 一个不为 None，返回 False
            else:
                return False

        return is_same_node(p, q)

• 时间复杂度：O(N)，其中 N 为树的节点数
• 空间复杂度：O(N)，其中 N 为树的节点数，当二叉树中每个节点只有一个孩子节点时，递归的层数为 N，此时空间复杂度为 O(N)

[Horace7]

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

[zcytm3000]

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)

[linlizzz]

思路

用递归算法：

1. 若两个都不为None，且两个的val相同，则将两者的左节点和右节点分别相对应继续作为两个子节点调用该函数，返回两者的and结果

2. 当两个节点都为None时则返回True

3. 其余情况（其中一个为None一个不为None，或两个都不为None，但两个的val不同）则返回False

代码

# 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 p and q and p.val == q.val:
            return (True and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right))
        elif p == None and q == None:
            return True
        else:
            return False

复杂度分析

T(n) = O(min(m,n)), m,n分别为两个树的节点数

S(n) = O(min(m,n))

[kyo-tom]

思路

dfs 或者 bfs 同时遍历两颗树即可

代码

/**
 * 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) {
        // return dfs(p, q);
        return bfs(p, q);
    }

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

    public boolean bfs(TreeNode p, TreeNode q) {
        Queue<TreeNode> pq = new LinkedList();
        Queue<TreeNode> qq = new LinkedList();
        if(p == null && q == null) {
            return true;
        }
        else if(p == null){
            return false;
        }
        else if(q == null){
            return false;
        }
        pq.offer(p);
        qq.offer(q);
        while (!pq.isEmpty() && !qq.isEmpty()) {
            TreeNode a = pq.poll();
            TreeNode b = qq.poll();
            if ( a.val == b.val) {
                if(a.left != null && b.left != null) {
                    pq.offer(a.left);
                    qq.offer(b.left);
                }
                else if ((a.left == null && b.left != null) 
                            ||  (a.left != null && b.left == null)) {
                                return false;
                            }
                if(a.right != null && b.right != null) {
                    pq.offer(a.right);
                    qq.offer(b.right);
                }
                else if ((a.right == null && b.right != null) 
                            ||  (a.right != null && b.right == null)) {
                                return false;
                            }
            }
            else {
                return false;
            }
        }
        if(pq.isEmpty() && qq.isEmpty()){
            return true;
        }
        else {
            return false;
        }
    }

}

复杂度分析

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

[RestlessBreeze]

code

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

    }
};

[Lydia61]

100. 相同的树

思路

使用递归的思想：当前节点的值相同，且左右子树为相同的树则为相同的树。如果遇到值不同的节点，或者树深度不一致则返回否。

代码

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

复杂度分析

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

[JasonQiu]

• Recurse root, left and 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
      return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

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

[JadeLiu13]

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)

[xiaoq777]

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

[franciszq]

思路

DFS

注意点

如果两个都为空，则返回true，如果有一个为空，则false，如果值不一样，则false

代码

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(1)

[JingYuZhou123]

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

[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))

[kangliqi1]

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

[snmyj]

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

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

[zhangjiahuan17]

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)

[lp1506947671]

思路

步骤一: 确定isSameTree(p,q)

步骤二:确定大问题和小问题间的关系isSameTree(p,q)=isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

步骤三:结束条件not p and not q 或者 not p or not q 或者p.val != q.val

代码

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)

复杂度

时间复杂度:O(N)

空间复杂度:O(h)

[CruiseYuGH]

关键点

• BFS ,递归的逻辑

代码

• 语言支持：Python3

Python3 Code:

# 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 p is None and q is None:
            return True
        if p is None or q is None:
            return False
        if p.val !=q.val:
            return False
        return self.isSameTree(p.right,q.right) and self.isSameTree(p.left,q.left)

复杂度分析

令 n 为数组长度。

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