Classic 150 Interview Questions P100 Same Tree

---

Timeline

Timeline

2025-10-23

init

Tree

---

Problem:

P100 Same Tree

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

Use recursion (preorder traversal). Two trees are the same if their root nodes are equal, and their left and right subtrees are also the same.

/**
 * 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 do it in one line because TreeNode implements PartialEq and Eq, 🤣🤣🤣

// 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() {}