博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetcode -- Binary Tree Preorder Traversal
阅读量:5834 次
发布时间:2019-06-18

本文共 1992 字,大约阅读时间需要 6 分钟。

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

For example:

Given binary tree {1,#,2,3},

1    \     2    /   3

 

return [1,2,3].

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

[解题思路]

递归解法

1 public ArrayList
preorderTraversal(TreeNode root) { 2 // IMPORTANT: Please reset any member data you declared, as 3 // the same Solution instance will be reused for each test case. 4 ArrayList
result = new ArrayList
(); 5 6 preorder(root, result); 7 8 return result; 9 }10 11 public void preorder(TreeNode root, ArrayList
result){12 if(root != null){13 result.add(root.val);14 preorder(root.left, result);15 preorder(root.right, result);16 }17 }

[非递归解法]

1)访问节点cur,并将节点cur入栈;

2)判断节点cur的左孩子是否为空,若为空,则取栈顶节点并进行出栈操作,并将栈顶节点的右孩子置为当前节点cur,循环至1);若不为空,则将cur的左孩子置为当前节点cur;

3)知道cur为null并且栈为空,则遍历结束

1 public ArrayList
preorderTraversal(TreeNode root) { 2 // IMPORTANT: Please reset any member data you declared, as 3 // the same Solution instance will be reused for each test case. 4 ArrayList
result = new ArrayList
(); 5 if(root == null){ 6 return result; 7 } 8 9 Stack
stack = new Stack
();10 TreeNode cur = root;11 while(cur != null || !stack.empty()){12 13 while(cur != null){14 result.add(cur.val);15 stack.push(cur);16 cur = cur.left;17 }18 19 if(!stack.empty()){20 cur = stack.pop();21 // if(cur.right != null){
22 cur = cur.right;23 // }24 }25 }26 27 return result;28 }

 

转载地址:http://hwucx.baihongyu.com/

你可能感兴趣的文章
Linux crontab定时执行任务
查看>>
mysql root密码重置
查看>>
33蛇形填数
查看>>
选择排序
查看>>
SQL Server 数据库的数据和日志空间信息
查看>>
前端基础之JavaScript
查看>>
自己动手做个智能小车(6)
查看>>
自己遇到的,曾未知道的知识点
查看>>
P1382 楼房 set用法小结
查看>>
分类器性能度量
查看>>
windows 环境下切换 python2 与 pythone3 以及常用命令
查看>>
docker 基础
查看>>
解决灾难恢复后域共享目录SYSVOL与NELOGON共享丢失
查看>>
eclipse集成weblogic开发环境的搭建
查看>>
写一个bat文件,删除文件名符合特定规则,且更改日期在某
查看>>
我的友情链接
查看>>
写Use Case的一种方式,从oracle的tutorial抄来的
查看>>
【C#】protected 变量类型
查看>>
Ubuntu解压
查看>>
爬虫_房多多(设置随机数反爬)
查看>>