[LeetCode] 94. Binary Tree Inorder Traversal

Problem

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

Example 1:

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

Example 2:

Input: root = []
Output: []

Example 3:

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

Constraints:

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

Solution

Logic

1. 이진 트리의 가장 좌측 하단으로 내려가면서 거쳐왔던 노드를 자료구조에 저장한다.

2. 리스트에 저장되지 않은 노드의 값을 리스트에 저장하고 우측 노드가 있으면 우측 노드로 내려가서 1번 과정부터 다시 수행한다. 우측 노드가 존재하지 않으면 1번에서 사용했던 자료구조를 통해 부모 노드로 돌아가고 다시 2번 과정을 수행한다.

3. 1번에서 사용했던 자료구조에 순회해야할 노드가 존재하지 않거나 처음부터 root노드가 비어있으면 순회를 멈춘다.

   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 List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) { // 순회해야할 노드가 Stack에 남아 있지 않거나, 처음부터 root가 비어있거나
            while (root != null) {
                stack.push(root);
                root = root.left;
            } root = stack.pop();
            list.add(root.val);
            root = root.right;
        } return list;
    }
   }
   

   Time Complextity

   • 이진 트리가 가진 노드의 개수를 n이라 할 때, 아래 반복문은 O(n)의 시간 복잡도를 가진다. 따라서 본 문제는 O(n)의 시간 복잡도를 가진다.

     List<Integer> list = new ArrayList<>();
     Stack<TreeNode> stack = new Stack<>();
     while (!stack.isEmpty() || root != null) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      } root = stack.pop();
      list.add(root.val);
      root = root.right;
     }