[리트코드] 100. Same Tree (tree)

문제 정보

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

Example 2:

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

문제 풀이

두 개의 트리를 동시에 순회하면서 다른 부분이 발견될 경우 false를 리턴한다.

 

 

Writeup

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q)
    {

        if (p == null && q == null) // both empty -> identical
        {
            return true;
        }
        else if (p == null || q == null) // one of them empty -> not identical
        {
            return false;
        }
        else if (p.val != q.val) // different -> not identical
        {
            return false;
        }
        else //recursion of traversal
        {
            bool left = IsSameTree(p.left, q.left);
            bool right = IsSameTree(p.right, q.right);

            return left && right;
        }
    }
}

 

 

 

 

 

출처 : https://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/

Write Code to Determine if Two Trees are Identical - GeeksforGeeks