Concise JAVA solution based on Stack


  • 0

    The basic idea is similar as binary tree inorder traverse, travel to each node's left child till reach the tree's left leaf, then switch to the higher node's right branch. As preorder sequence is root, left, right, so the difference in this solution from inorder solution is adding node's value to the result during traveling to left leaf, instead of reaching left leaf.

    public ArrayList<Integer> preorderTraversal(TreeNode root) {
    	ArrayList<Integer>res = new ArrayList<Integer>();
    	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
    			res.add(cur.val);
    			stack.push(cur);
    			cur = cur.left;
    		}		 
    		cur = stack.pop(); // Backtrack to higher level node A
    		cur = cur.right;   // Switch to the higher node A's right branch 
    	}
    	return res;
    }

Log in to reply
 

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