[LeetCode] Binary Tree Inorder TraversalSolution

링크 : 

leetcode.com/problems/binary-tree-inorder-traversal/

Binary Tree Inorder Traversal - LeetCode

---

이진 트리의 루트가 주어지면 노드 값의 순회하고, 순회를 반환합니다.

 

조건 :

1. 트리의 노드 수는 [0, 100] 범위에 있습니다. 

2. -100 <= Node.val <= 100

 

참고 : 재귀 풀이 보다 반복에 염두해두고 푸세요.?

 

Example 1:

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

Example 2:

Input: root = [] Output: []

Example 3:

Input: root = [1] Output: [1]

Example 4:

Input: root = [1,2] Output: [2,1]

Example 5:

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

 

---

구현 전에 알아본 이진트리

 

트리구조란?

노드와 노드의 연결

그래프 자료구조의 일종이다.

 

노드란?

정보의 단위, 정보를 가진 개체

 

데이터베이스 또는 파일 시스템등에서 많은 양의 데이터를 관리하기 위한 목적으로 사용된다.

 

특징

• 트리는 부모 노드와 자식 노드의 관계로 표현된다.
• 트리의 최상단 노드는 루트노드(Root Node)라고 한다.
• 트리 최하단 노드를 단말 노드(Leaf)라고 한다.
• 트리에서 일부를 떼어내도 트리 구조이며 이를 서브트리(SubTree)라고 한다.
• 트리는 파일시스템과 같이 계층, 정렬된 데이터이다.

---

이진탐색 (Binary search)

 

반으로 쪼개면서 탐색한다.

 

배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

데이터가 무작위면 사용할 수 없지만 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다.

이진 탐색은 탐색 범위를 절반씩 좁히며 데이터를 찾는다.

위치를 나타내는 세 가지 변수 : start, end, middle

찾으려는 데이터(Target)과 middle을 반복 비교한다.

 

github.com/devjun63/codingTest-dongbinna/blob/master/src/main/java/devjun/codingTestdongbinna/binarySearch/BinarySearchExamImpl.java

devjun63/codingTest-dongbinna

---

이진 탐색 트리 (Binary search Tree)

• 트리 자료구조 중에서 가장 간단한 형태이다.
• 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조이다.

특징

• 부모 노드보다 왼쪽 자식 노드가 작다.
• 부모 노드보다 오른쪽 자식 노드가 크다.
• 왼쪽 자식노드 < 부모노드 < 오른쪽 자식 노드

---

 

구현시 Node 클래스를 만들고 left, data, pointer, right 네 가지 field를 사용해 구현하면 된다고 한다.

시작 시간 2021-03-10 오후 10:05 종료 시간 10:43분

문제를 보니 Tree는 이미 구현되어있고 그 구현체를 Inorder하는 것이 목적이다.

Inorder(중순위 순회)의 기본 규칙        

왼쪽 부트리를 TL 루트를 R 오른쪽 부트리를 TR로 선언

1. TL 순회
2. R 순회
3. TR 순회

sudo 코드

if x != null
 then inorderTreeWalk(left[x]);
 	  print(x);
      inorderTreeWalk(right[x]);

 

첫번째 시도 missmatch type int != null은 비교 불가

class Solution {
    // LinkedList 선언
    static List<Integer> inorderList = new ArrayList();
    public List<Integer> inorderTraversal(TreeNode root) {
        
        /*
        중순위 순회 inorder 기본 규칙
        왼쪽 부트리를 TL 루트를 R 오른쪽 부트리를 TR로 선언
        1. TL 순회
        2. R 순회
        3. TR 순회
        */
        if(root.val != null)
        {
            inorderTraversal(root.left);
            inorderList.add(root.val);
            inorderTraversal(root.right); 
        }
        return inorderList;
    }
}

두번째 Integer로 boolean과 비교 -> nullpointerException

class Solution {
    // LinkedList 선언
    static List<Integer> inorderList = new ArrayList();
    public List<Integer> inorderTraversal(TreeNode root) {
        
        /*
        중순위 순회 inorder 기본 규칙
        왼쪽 부트리를 TL 루트를 R 오른쪽 부트리를 TR로 선언
        1. TL 순회
        2. R 순회
        3. TR 순회
        */
        Integer temp = new Integer(root.val);
        if(temp != null)
        {
            inorderTraversal(root.left);
            System.out.println(root.val);
            inorderTraversal(root.right); 
        }
        return inorderList;
    }
}

세번째 요소의 위치 확인

/**
 * 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 {
    // LinkedList 선언
    static List<Integer> inorderList = new ArrayList();
    public List<Integer> inorderTraversal(TreeNode root) {
        
        /*
        중순위 순회 inorder 기본 규칙
        왼쪽 부트리를 TL 루트를 R 오른쪽 부트리를 TR로 선언
        1. TL 순회
        2. R 순회
        3. TR 순회
        */
        System.out.println(root.val);
        System.out.println(root.right.val);
        System.out.println(root.right.left.val);
        
        /*
        Integer temp = new Integer(root.val);
        if(temp != null)
        {
            inorderTraversal(root.left);
            System.out.println(root.val);
            inorderTraversal(root.right); 
        }
        */
        return inorderList;
    }
}

네번째 try and catch로 npe 탈출 -> 성공

/**
 * 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 {
    // LinkedList 선언
    public List<Integer> inorderList = new ArrayList();
    public List<Integer> inorderTraversal(TreeNode root) {
        Integer temp = null;
        /*
        중순위 순회 inorder 기본 규칙
        왼쪽 부트리를 TL 루트를 R 오른쪽 부트리를 TR로 선언
        1. TL 순회
        2. R 순회
        3. TR 순회
        */
        try
        {
            temp = new Integer(root.val);
        }
        catch(NullPointerException e){} //e.printStackTrace() 사용하면 17ms까지 올라감
        
        /*
        System.out.println(root.val);
        System.out.println(root.right.val);
        System.out.println(root.right.left.val);
        */
        
        if(temp != null)
        {
            inorderTraversal(root.left);
            inorderList.add(root.val);
            inorderTraversal(root.right); 
        }
        
        return inorderList;
    }
}
//3ms and 37.5 MB사용

Runtime: 3 ms, faster than 12.79% of Java online submissions for Binary Tree Inorder Traversal.
Memory Usage: 37.5 MB, less than 34.59% of Java online submissions for Binary Tree Inorder Traversal.

---

참고 영상

 

www.youtube.com/watch?v=TdakkF5Xh6o