leetcode257 Binary Tree Paths

题目

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are: [“1->2->5”, “1->3”] 需要得到所有从根到叶子结点的路径。

解题思路

既然是得到路径,那么很自然的想到使用深度优先遍历(DFS),DFS在二叉树中对应的就是前序遍历,然后用一个ArrayList保存访问过的节点,就可以了。

public class leetcode257 {
    private ArrayList<Integer> record = new ArrayList<>();
    private List<String> res = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        helper(root);
        return res;
    }

    private void helper(TreeNode node) {
        if (node != null) {
            //节点加入记录
            record.add(node.val);
            helper(node.left);
            helper(node.right);
            if (node.left == null && node.right == null) {
                //叶子结点,打印输出记录里所有节点.
                String temp = "";
                for (int i = 0; i < record.size(); i++) {
                    if (i == 0) temp += record.get(i);
                    else
                        temp = temp + "->" + record.get(i);
                }
                res.add(temp);
            }
            //此时,该节点左右子树都已经打印输出完毕,可以从记录中删除
            record.remove(record.size() - 1);
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

剑指Offer-把二叉树打印成多行

package Tree; import java.util.ArrayList; import java.util.LinkedList; import ...

3414
来自专栏noteless

[四] java8 函数式编程 收集器浅析 收集器Collector常用方法 运行原理 内部实现

收集器是由四个函数约定构成,它们一起工作,将条目汇集到一个可变的结果容器中,并可选择性地对结果执行最终转换。

922
来自专栏计算机视觉与深度学习基础

Leetcode 214. Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding chara...

1938
来自专栏冷冷

基于Redis实现分布式应用限流

限流的目的是通过对并发访问/请求进行限速或者一个时间窗口内的的请求进行限速来保护系统,一旦达到限制速率则可以拒绝服务。 前几天在DD的公众号,看了一篇关于使用 ...

4558
来自专栏Jed的技术阶梯

Spark常用Transformations算子(二)

介绍以下Transformations算子: aggregateByKey join cogroup cartesian pipe repartit...

784
来自专栏刘望舒

LeakCanary看这一篇文章就够了

LeakCanary是Square公司基于MAT开源的一个内存泄漏检测工具,在发生内存泄漏的时候LeakCanary会自动显示泄漏信息。

1795
来自专栏博岩Java大讲堂

Java集合--TreeMap完全解析

6014
来自专栏码匠的流水账

聊聊sentinel的DegradeSlot

com/alibaba/csp/sentinel/slots/block/degrade/DegradeSlot.java

581
来自专栏函数式编程语言及工具

FunDA(5)- Reactive Streams:Play with Iteratees

    FunDA的设计目标就是把后台数据库中的数据搬到内存里,然后进行包括并行运算的数据处理,最后可能再对后台数据库进行更新。如果需要把数据搬到内存的话,那我...

18810
来自专栏Java 源码分析

二叉搜索树

一、操作: 判断元素是否存在:递归的在左右子树中查找 查找最小元素:在左子树中递归或者循环 查找最大元素:在右子树中递归或循环 插入:递归的插入,大于则插入在节...

2685

扫码关注云+社区