DEV Community

Cover image for Same Tree
FakeStandard
FakeStandard

Posted on

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
or buy me a coffee ⬇️ I'd appreciate it.

Buy-me-a-coffee


Top comments (0)