Concise JAVA solution based on Stack


  • 32

    Explanation

    The basic idea is referred from here: using stack to simulate the recursion procedure: for each node, travel to its left child until it's left leaf, then pop to left leaf's higher level node A, and switch to A's right branch. Keep the above steps until cur is null and stack is empty. As the following:

    Runtime = O(n): As each node is visited once

    Space = O(n)

    public List<Integer> inorderTraversal(TreeNode root) {
    	List<Integer> res = new LinkedList<Integer>();
    	if (root == null) return res;
    	
    	Stack<TreeNode> stack = new Stack<TreeNode>();
    	TreeNode cur = root;
    	while (cur != null || !stack.isEmpty()) { 
    		while (cur != null) {// Travel to each node's left child, till reach the left leaf
    			stack.push(cur);
    			cur = cur.left;				
    		}		 
    		cur = stack.pop(); // Backtrack to higher level node A
    		res.add(cur.val);  // Add the node to the result list
    		cur = cur.right;   // Switch to A'right branch
    	}
    	return res;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.