[LeetCode]226.Invert Binary Tree(java,python)

Invert Binary Tree - LeetCode

이진트리가 주어졌을 때 이를 역전시켜라 ( 좌 우를 )

(50)

풀이 방법 ( java)

leaf node 바로 위 노드부터 시작 ( level 이 depth -1 인 노드에 도달 ) 하여

좌우를 swap한다.

• 나는 “👏아래 → 위”로 올라가면서 풀었다. 그런데 “위→아래” 로도 풀 수 있는 거였음. ( 머리로는 이해가 가는데, 이런거에 약하니, 매 번 생각해 볼 것 )
  • leaf node보다 위의 노드인 경우, left child, right child를 swap 시켰다.
  • 값만을 swap 하는게 아니라, 아예 참조값을 swap 시켜야함. 처음부터 참조값을 swap시켜야된다고 생각했던 것은, 단순히, null이 노드를 다루기 귀찮았기 때문이었는데, 다행히도 참조값 자체를 swap시키는게 맞았어서, null도 그저 swap 될 뿐이었다.

내가 고민했던 부분이 아래그림과 같았는데

• 값만을 swap한다며 오른쪽그림
• 참조값 자체를 swap한다면 왼쪽그림이 된다.

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        dfs(root);
        return root;
        
    }
    // -1 -> null
    // Otherwise -> 1 
    public int dfs(TreeNode cur){
        // 현재 노드가 null인 경우 
        if(cur == null) return -1;
        int left = dfs(cur.left);
        int right = dfs(cur.right);
        // 현재 노드가 leaf 노드인 경우 
        if(left == -1 && right == -1) return 1;
        // Otherwise 
        if(left != -1 || right != -1){
            // left child, right child 자체를 swap 
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
        }
        return 1;
    }
}

책의 다양한 풀이 ( python )

• 위의 방식처럼 재귀적으로 푸는 방식 . 단 위 → 아래

처음 안 거

python에서 다음 줄에 instruction 작성하려면 “\” 를 쓰면 된다고 함

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        # 위 -> 아래로 내려가는 방식 
        if root is None:
            return None
        root.left,root.right = \
            self.invertTree(root.right),self.invertTree(root.left)
        return root

• 반복구조로 BFS 를 사용하여 풀 수도 있다고 함 . 그냥, q 에다가 굳이 current node를 집어넣는 과정이 추가된것..
  • 이것도 똑같이 위→ 아래로 하향식으로 swap 을 해 나가는 것.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        q = collections.deque([root])
        while q:
            node = q.popleft()
            # 위 -> 아래
            if node:
                node.left,node.right = node.right,node.left
                q.append(node.left)
                q.append(node.right)
        return root