Cover image for Interview Classic 150 Questions P100 Same Tree

Interview Classic 150 Questions P100 Same Tree

(Updated: )
algorithm
, ,
Timeline

timeline

2025-10-23

init

tree

Title:

P100 Same Tree

https://leetcode.cn/problems/same-tree/description/?envType=study-plan-v2&envId=top-interview-150

Recursive traversal, preorder traversal. If two trees are the same, then their root nodes must be the same, and their left subtrees are the same, and their right subtrees are also the same.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * 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) {}
 * };
 */

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

Rust can be done in one line because TreeNode implements PartialEq, Eq, 🤣🤣🤣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}
use std::cell::RefCell;
use std::rc::Rc;
struct Solution;
impl Solution {
    pub fn is_same_tree(
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> bool {
        p == q
    }
}
fn main() {}