DEV Community

Cover image for Same Tree
FakeStandard
FakeStandard

Posted on • Edited on

2

Same Tree

#100.Same Tree

Problem statement

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.

Example 1

Input: p = [1,2,3], q = [1,2,3]
Output: true
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: p = [1,2], q = [1,null,2]
Output: false
Enter fullscreen mode Exit fullscreen mode

Explanation

給定兩個二元樹的樹根 pq ,檢查兩個二元樹是否相同,相同的定義為結構相同、節點也具有相同的值,最終返回 truefalse

Solution

有關二元樹的題目,解法通常離不開遞迴,這題要比較兩個二元樹結構是否完全相同,用遞迴可寫出優雅的解法,一開始先判斷二元樹是否為 null,若其中一個是 null,返回兩者是否相等的判斷結果,若兩個節點都不是 null,則比較兩者節點值是否相同,若不同則在最底部返回 false,若節點值相同則繼續走訪左子樹和右子樹,呼叫自己 IsSameTree 並傳入要比較的對應節點,直到判斷完成

public bool IsSameTree(TreeNode p, TreeNode q)
{
    if (p == null || q == null) return p == q;

    if (p.val == q.val)
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);

    return false;
}
Enter fullscreen mode Exit fullscreen mode

Reference

LeetCode Solution

GitHub Repository


Thanks for reading the article 🌷 🌻 🌼

If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub ⭐ I'd appreciate it.


Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

AWS GenAI LIVE!

GenAI LIVE! is a dynamic live-streamed show exploring how AWS and our partners are helping organizations unlock real value with generative AI.

Tune in to the full event

DEV is partnering to bring live events to the community. Join us or dismiss this billboard if you're not interested. ❤️