Stack<TreeNode> s = new Stack<TreeNode>();
public List<int> preorderTraversal (TreeNode root) {
List<int> list = new List<int>();
if(root == null) //为空直接返回
{
return list;
}
TreeNode now = root;
while(now != null || s.Count !=0)
{
if(now != null)
{
list.Add(now.val);
s.Push(now);
now = now.left;
}
else
{
now = s.Pop();
now = now.right;
}
}
return list;
}
递推实现方式
用栈存储当前遍历到的结点,先往左边遍历,当遇到空时回到上一个结点,然后往右遍历,回到循环上面后继续一样的操作;如果右子树为空会返回更上一级和递归一样。