首页 > 代码库 > 40: Binary Tree Preorder Traversal
40: Binary Tree Preorder Traversal
/************************************************************************/
/* 40: Binary Tree Preorder Traversal */
/************************************************************************/
/*
* 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].
* */
/****前序遍历 preOrder tree 递归方法实现的*** Time: O(n), Space: O(n).*****************************************************************/
/*
* 应用1： 文件目录显示：
* 显示文件夹时，子文件夹缩进，同级的文件夹缩进相同距离，适合使用前序遍历
* */
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> source=new ArrayList<Integer>(); String str=""; preorderTree(root,source,str); return source; } private void preorderTree(TreeNode node,List<Integer> nodes,String str) { if(node==null) { return; } str+="--------"; System.out.println(str+"---->"+node.val); nodes.add(node.val); preorderTree(node.left,nodes,str); preorderTree(node.right,nodes,str); } /****前序遍历 preOrder tree Time: O(n), Space: O(n) 栈迭代方法实现的********************************************************************/ /* * root-- left --right * */ public List<Integer> preorderTraversal2(TreeNode root) { List<Integer> results=new ArrayList<Integer>(); Stack<TreeNode> stack=new Stack<TreeNode>(); stack.push(root); TreeNode node=null; while(!stack.isEmpty()) { node=stack.pop(); results.add(node.val); if(node.right!=null) { stack.push(node.right); } if(node.left!=null) { stack.push(node.left); } } return results; } /**Threaded tree (Morris)***Time: O(n), Space: O(1)*******************************************************************/ /*二叉树的Morris遍历可不使用用栈，在常量空间O(1)、线性时间O(n)内实现二叉树的前中后序遍历，且遍历后不破坏二叉树的形状（中间过程允许改变其形状）。Morris遍历的基本原理是利用所有叶子结点的right指针，指向其后继结点，组成一个环，在第二次遍历到这个结点时，由于其左子树已经遍历完了，则访问该结点。 * */
40: Binary Tree Preorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。