一、栈 - AndyJuan/Algorithm GitHub Wiki
1.1 前序遍历——leetcode 144 https://leetcode-cn.com/problems/binary-tree-preorder-traversal/ 递归算法
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<Integer>();
preOrder(root,list);
return list;
}
public void preOrder(TreeNode root, List<Integer> list){
if (root == null){
return;
}
list.add(root.val);
preOrder(root.left,list);
preOrder(root.right,list);
}
复杂度分析
时间复杂度：O(n)O(n)，其中 nn 是二叉树的节点数。每一个节点恰好被遍历一次。
空间复杂度：O(n)O(n)，为递归过程中栈的开销，平均情况下为 O(\log n)O(logn)，最坏情况下树呈现链状，为 O(n)O(n)。
迭代算法（栈）
首先我们应该创建一个Stack用来存放节点，首先我们想要打印根节点的数据，此时Stack里面的内容为空，所以我们优先将头结点加入Stack，然后打印。
之后我们应该先打印左子树，然后右子树。所以先加入Stack的就是右子树，然后左子树。
public List<Integer> preorderTraversal1(TreeNode root) {
List<Integer> list = new LinkedList<Integer>();
if (root == null){
return list;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
list.add(node.val);
if (node.right!= null){
stack.push(node.right);
}
if (node.left!=null){
stack.push(node.left);
}
}
return list;
}