LeetCode 94. Binary Tree Inorder Traversal

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

For example: Given binary tree [1,null,2,3],

1 \ 2 / 3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

解题思路：先定义一个栈，从根节点开始，找到最左边节点，并在找最左节点时，将最左边节点的所有祖先节点进栈。找到最左节点后，将该节点放入list中，再对该节点的右孩子进行循环处理。主要注意的是循环的结束条件，栈不空，表示有节点没有进入list中，指向当前处理节点的指针不为空，表示还有节点没有处理完。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list= new ArrayList<Integer>(); if(root!=null){ Stack<TreeNode> stack= new Stack<TreeNode>(); //先把根节点进栈 // stack.push(root); //出栈 TreeNode p=root; //栈不空，表示有节点没有访问 while(!stack.empty() || p!=null ){ //当前出栈节点有左孩子 while(p!=null){ stack.push(p); p=p.left; } //while循环结束时，表示已经到了最左边叶子节点的左孩子了 p=stack.pop(); list.add(p.val); //将最左孩子的值加入list中 p=p.right; } } return list; } }