More:【目录】LeetCode Java实现
https://leetcode.com/problems/binary-tree-preorder-traversal/
Given a binary tree, return the preordertraversal of its nodes‘ values.
Example:
Input:[1,null,2,3]1 2 / 3 Output:[1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
Stack
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stk = new Stack<>();
while(root!=null || !stk.isEmpty()){
while(root!=null){
list.add(root.val);
stk.push(root);
root=root.left;
}
root=stk.pop().right;
}
return list;
}
OR
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stk = new Stack<>();
stk.push(root);
while(!stk.isEmpty()){
TreeNode node = stk.pop();
if(node==null)
continue;
list.add(node.val);
stk.push(node.right);
stk.push(node.left);
}
return list;
}
Time complexity : O(n)
Space complexity : O(nlogn)
More:【目录】LeetCode Java实现
【LeetCode】144. Binary Tree Preorder Traversal
原文：https://www.cnblogs.com/yongh/p/11791177.html