Python으로 푸는 LeetCode 965. Univalued Binary Tree (Easy)

2진 트리에서 모든 노드가 같은 값을 가지고 있는지

확인하는 프로그램을 짜시오.

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

Github에서 코드 보기

문제 풀이

leetcode에서는 기본 자료구조를 잘 활용할 수 있도록 다양한 문제를 준다. 이 문제도 트리의 순회문제이다. 순회를 할 때는 재귀를 이용할 수 있고 While문을 이용해서 모든 노드를 탐색할 수 있다. 나는 두가지 방식 모두를 활용해서 문제를 풀어보았다. 재귀를 별로 좋아하진 않은데 while문과 재귀 모두를 짜보게 되면 문제를 한단계 깊게 생각할 수 있어서 좋다. 

파이썬 코드

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
 
# while loop
class Solution:
    def isUnivalTree(self, root) -> bool:
        node_list = [root]
        while node_list:
            cnode = node_list.pop()
            if cnode.val == root.val:
                if cnode.left: node_list.append(cnode.left)
                if cnode.right: node_list.append(cnode.right)
            else:
                return False
        return True
 
 
# Recursion
class Solution:
    def isUnivalTree(self, root) -> bool:
        if root:
            if root.left:
                if root.val != root.left.val:
                    return False
 
            if root.right:
                if root.val != root.right.val:
                    return False
        else:
            return True
        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)
 
 
 
if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(1)
    root.right = TreeNode(1)
    lnode = root.left
    rnode = root.right
    lnode.left = TreeNode(1)
    lnode.right = TreeNode(1)
    rnode.right = TreeNode(1)
 
 
    s = Solution()
    print(s.isUnivalTree(root))