💛 오늘의 학습 키워드

[DFS/BFS] Binary Tree Inorder Traversal

📝 문제

문제 설명

Given the root of a binary tree, return the inorder traversal of its nodes' values.

제한 조건

• The number of nodes in the tree is in the range [0, 100].
• -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]

💬 내 풀이

/**
 * 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 {
    List<Integer> list;

    public List<Integer> inorderTraversal(TreeNode root) {
        list = new ArrayList<Integer>();

        inorder(root);
        return list;
    }

    public void inorder(TreeNode node) {
        if(node != null) {
            if(node.left != null) { inorder(node.left); }
            list.add(node.val);
            if(node.right != null) { inorder(node.right); }
        }
    }
}

💻 내 접근 방법

1. 이 문제는 중위 순회한 값을 리턴하는 문제이다.

   중위 순회
   Left > Root > Right 순으로 탐색한다.
   전위 순회
   Root > Left > Right 순으로 탐색한다.
   후위 순회
   Left > Right > Root 순으로 탐색한다.

2. list 를 선언한 후, null이 아닌 값을 찾아서, 왼쪽값, 노드값, 오른쪽 값을 순차적으로 list 에 넣는다.

✨ 다른 사람 풀이

class Solution {
	public List<Integer> inorderTraversal(TreeNode root) {
    
      List<Integer> answerList = new ArrayList<>(;
      Stack<TreeNode> tempStack = new Stack<>;
      TreeNode curr = root;
      
      while(curr != null || !tempStack.isEmpty()){
        while(curr != null){
          tempStack. push (curr);
          curr = curr.left;
      	}
      	curr = tempStack.pop;
      	answerList. add (curr.val);
      	curr = curr.right;
      }
      
  	  return answerlist;
  }
}

1. 재귀방식을 사용하지 않고, stack 방식을 사용해서 작성한 코드이다.
2. left 부터 tempStack에 현재 탐색하고 있는 부분노드를 넣고, 말단노드까지 도달했다면(=null) 나오면서 rignt 값이 존재하는지 탐색하고 부모 노드를 다시 꺼내서 점차 상위로 이동하면서 탐색하는 과정을 반복한다.

💦 회고

오히려 stack 으로 구현하는게 아직은 더 어려운 것 같다.