144. Binary Tree Preorder Traversal (二叉树前序遍历)


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

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

   1
\
2
/
3

return [1,2,3].

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

递归 :

 class Solution {
private List<Integer> res = new ArrayList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
help(root);
return res;
}
private void help(TreeNode root){
if(root == null) return ;
res.add(root.val);
help(root.left);
help(root.right);
}
}

非递归:

终极版:

 class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack<TreeNode>();
List<Integer> res = new ArrayList<Integer>();
while(root!=null||!s.isEmpty()){
while(root!=null){
s.push(root);
res.add(root.val);
root = root.left;
}
if(!s.isEmpty()){
root = s.pop();
root = root.right;
}
}
return res;
}
}
 class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>(); //用stack 来保存 右子树
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
res.add(cur.val);
stack.add(cur.right);
cur = cur.left;
}
cur = stack.pop();
}
return res;
}
}

20180320

用stack 保存右节点跟左节点

 class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack();
stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
if (root!=null){
res.add(root.val);
stack.push(root.right);
stack.push(root.left);
}
}
return res;
}
}
上一篇:iptables的例子1


下一篇:js,jq新增元素 ,on绑定事件无效