[LeetCode] 101. Symmetric Tree

Problem

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

Solution

Logic

1. 뿌리 노드의 왼쪽 자식 노드와 오른쪽 자식노드부터 내려가면서, 비교해야 하는 대칭상의 두 노드의 값을 반복을 통해 비교한다.

2. 트리의 아래로 내려가면서, 비교해야 하는 두 노드의 값이 다르거나 두 노드 중 하나 이상이 null인 경우에 반복을 중지한다.

   Code

   /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode() {}
    *     TreeNode(int val) { this.val = val; }
    *     TreeNode(int val, TreeNode left, TreeNode right) {
    *         this.val = val;
    *         this.left = left;
    *         this.right = right;
    *     }
    * }
    */
   class Solution {
    public boolean isSymmetric(TreeNode root) {
        return hasSameValue(root.left, root.right);
    }
    private boolean hasSameValue(TreeNode left, TreeNode right) {
        if (left == null || right == null) return left == right; // 두 노드 중 하나 이상이 null인 경우
        else if (left.val != right.val) return false; // 두 노드의 값이 다른 경우
        return hasSameValue(left.left, right.right) && hasSameValue(left.right, right.left);
    }
   }
   

   Time Complexity