100. Same Tree

  • Hardness: \(\color{green}\textsf{Easy}\)
  • Ralated Topics: Tree、Depth-First Search、Breadth-First Search、Binary Tree

一、題目

Given the roots of two binary tree p and q, write a function to check if they are the same or not.
Two binary tree are considered the same if they are structurally iedntical, and the nodes have the same value.

Example 1:
ex1

  • Input: p = [1,2,3], q = [1,2,3]
  • Output: true

Example 2:
ex2

  • Input: p = [1,2], q = [1,null,2]
  • Output: false

Example 3: ex3

  • Input: p = [1,2,1], q = [1,1,2]
  • Output: false

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -10^4 <= Node.val <= 10^4

二、分析

  • 典型樹的遍歷問題，兩棵樹一起遍歷，注意要處理當 node == null 的情形便可。
  • 兩棵樹相同的條件為：root 的值相同，且左右兩個 leaf 也相同。

三、解題

1. Recursion

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
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);
}

回目錄 Catalog