leetcode 257. 二叉树的所有路径 包含（二叉树的先序遍历、中序遍历、后序遍历）
2024-09-05 08:34:43
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
首先来看递归版本：
static void dfs(TreeNode root, String path, LinkedList<String> paths){
if(root.left == null && root.right ==null){
paths.add(path + root.val);
return;
}
if(root.left != null) {
dfs(root.left, path + root.val + "->", paths);
}
if(root.right != null ) {
dfs(root.right, path + root.val + "->", paths);
}
}
public static List<String> binaryTreePaths(TreeNode root) {
LinkedList<String> paths = new LinkedList();
//递归版本
// dfs(root, "", paths);
return paths;
}
那么如何将其改为非递归版本呢，我们利用后序遍历模板与先序遍历模板来实现。
解法一
static void iteration(TreeNode root, LinkedList<String> paths) {
Stack<TreeNode> s = new Stack<>();
TreeNode p = root;
TreeNode pre = null;
while(p != null ){
s.push(p);
p = p.left ;
}
while(!s.empty()){
p = s.peek();
if(p.right!=null && p.right != pre){
p = p.right;
while(p != null ){
s.push(p);
p = p.left ;
}
pre =null;
}
else{
if(pre == null ) {
paths.add(getPath(s, "->"));
}
pre = s.pop();
}
}
System.out.println();
}
public static List<String> binaryTreePaths(TreeNode root) {
LinkedList<String> paths = new LinkedList();
//递归版本
// dfs(root, "", paths);
//非递归版本
iteration(root, paths);
return paths;
}
private static String getPath(Stack<TreeNode> s, String sp) {
// Iterator<TreeNode> it = s.iterator();
StringBuilder buf = new StringBuilder();
// while (it.hasNext()) {
// if (buf.length() != 0) {
// buf.append(sp);
// }
// buf.append(String.valueOf(it.next().value));
// }
for(TreeNode node : s){
if (buf.length() != 0) {
buf.append(sp);
}
buf.append(String.valueOf(node.val));
}
return buf.toString();
}
解法二
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
LinkedList<String> paths = new LinkedList();
if (root == null)
return paths;
LinkedList<TreeNode> node_stack = new LinkedList();
LinkedList<String> path_stack = new LinkedList();
node_stack.add(root);
path_stack.add(Integer.toString(root.val));
TreeNode node;
String path;
while (!node_stack.isEmpty()) {
node = node_stack.pollLast();
path = path_stack.pollLast();
if ((node.left == null) && (node.right == null))
paths.add(path);
if (node.left != null) {
node_stack.add(node.left);
path_stack.add(path + "->" + Integer.toString(node.left.val));
}
if (node.right != null) {
node_stack.add(node.right);
path_stack.add(path + "->" + Integer.toString(node.right.val));
}
}
return paths;
}
}
在这里我们用两种模板完整地实现二叉树的先序遍历，中序遍历，后序遍历。
思想一： 在从栈里弹出节点的时候，此时压入左右节点
public static void PreOrderTraversal(TreeNode root){
Stack<TreeNode> s = new Stack<>();
TreeNode p = root;
s.push(p);
while(!s.empty()){
TreeNode node = s.pop();
if(node == null ){
continue;
}
System.out.print(node.val+" ");
if(node.right != null ) {
s.push(node.right);
}
if(node.left != null ){
s.push(node.left);
}
}
System.out.println();
}
public static void PostOrderTraversal(TreeNode root){
List<Integer> res = new ArrayList<>();
Stack<TreeNode> s = new Stack<>();
TreeNode p = root;
s.push(p);
while(!s.empty()){
TreeNode node = s.pop();
if(node == null ){
continue;
}
// System.out.print(node.val+" ");
res.add(node.val);
if(node.left != null ) {
s.push(node.left);
}
if(node.right != null ){
s.push(node.right);
}
}
Collections.reverse(res);
System.out.println(res);
}
思想二： 从栈中弹出节点的时候，一直压入左孩子，直到为空，对于栈顶节点来说，如果有右孩子，压入右孩子，否则一直弹。
后序遍历比较特殊，对于某一节点来说，需要判断是从左右节点哪个节点访问。
public static void PreOrderWithoutRecursion(TreeNode root){
Stack<TreeNode> s = new Stack<>();
TreeNode p = root;
while(p != null || !s.empty()){
if(p != null ){
System.out.print(p.val +" ");
s.push(p);
p = p.left ;
}
else{
p = s.pop();
p = p .right;
}
}
System.out.println();
}
public static void InOrderWithoutRecursion(TreeNode root){
Stack<TreeNode> s = new Stack<>();
TreeNode p = root;
while(p != null || !s.empty()){
if(p != null ){
s.push(p);
p = p.left ;
}
else{
p = s.pop();
System.out.print(p.val +" ");
p = p.right;
}
}
System.out.println();
}
public static void PostOrderWithoutRecursion(TreeNode root){
Stack<TreeNode> s = new Stack<>();
TreeNode p = root;
TreeNode pLastVistNode = null;
while(p != null ){
s.push(p);
p = p.left ;
}
while(!s.empty()){
p = s.pop();
if( p.right == null || p.right == pLastVistNode){
System.out.print(p.val+" ");
pLastVistNode = p;
}
else{
s.push(p);
p = p.right;
while(p != null){
s.push(p);
p = p.left;
}
}
}
System.out.println();
}
最新文章
- MySQL 代码开发注意事项----开发高性能的sql
- 【webGL】threejs常用的api
- C语言拾遗（一）
- 关于前端build工具
- 动态改变actionbar上menu的图标
- mm/vmalloc.c
- 兼容所有浏览器---无缝上下左右交叉运动----原生js+css
- 在eclipse中安装activiti插件
- ShareSDK 社会化分享 集成步骤
- jTDS驱动兼容性问题
- iOS如何提高页面流畅度
- SQL server 多个字段设为主键
- Perl处理数据(一)：s替换、split和join
- 朱晔的互联网架构实践心得S1E10：数据的权衡和折腾【系列完】
- iOS开发笔记－根据frame大小动态调整fontSize的自适应文本及圆形进度条控件的实现
- SOA架构大概思路
- 弄清SDI显示工程中的每一个信号，每一个逻辑
- python读写json+字典保存
- 解决CentOS下无法发送邮件的问题
- 【jsp】Servlet与jsp之间的传值