[leetcode] 94. Binary Tree Inorder Traversal

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]

sol1

public List<Integer> inorderTraversal(TreeNode root){
	List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>(); // stack 에 임시로 저장했다가 
    // 조건을 걸어서 pop 시킨 뒤 list 에 저장한다. 
    // current node --> root 
    TreeNode cur = root;
    
    while(cur != null || !stack.empty()){ // 현재 노드 혹은 스택이 비어있지 않을 때에만 while문 실행 
    	while(cur!=null){ // 현재 노드로 지정된 노드가 존재할 때만 while문 실행
        	stack.add(cur); // stack 에 현재 노드를 저장한다 .
            cur = cur.left; // 스택에 객체를 저장하고, 현재 노드는 이제 왼쪽 노드를 가리킨다. 
            // 모든 TreeNode 객체가 스택에 저장될 때 까지 while 문을 반복한다. 
    	}
        
        cur = stack.pop(); // stack 에서 가장 마지막으로 저장된 객체를 꺼낸다. 
        list.add(cur.val); // 그 노드 객체의 val 을 리스트에 저장한다. 
        cur = cur.right; // 현재 노드는 이제 오른쪽 노드를 가리킨다. 
        
   	}
    
    return list;
 }