Middle order traversal of binary trees

Leetcode-cn.com/problems/bi…

Their thinking

Method one: recursion

List<Integer> res = new LinkedList<Integer>();
public List<Integer> inorderTraversal(TreeNode root) {
	if(root ! =null) {
		inorderTraversal(root.left);
		res.add(root.val);
		inorderTraversal(root.right);
	}
	return res;
}  
Copy the code

Method two: iteration

Description: recursion in the bottom of the implementation is to use the stack, with the iterative method is just the bottom of the stack manifest.

public List<Integer> inorderTraversal(TreeNode root) {
	List<Integer> res = new LinkedList<Integer>();
	Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
	while(! stack.isEmpty() || root ! =null) {
		// Go all the way down the left subtree, pushing all the nodes iterated in the process
		while(root ! =null) {
			stack.push(root);
			root = root.left;
		}
		root = stack.poll();
		res.add(root.val);
		root = root.right;
	}
	return res;
}
Copy the code