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 条评论
登录 后参与评论

相关文章

来自专栏彭湖湾的编程世界

【算法】论平衡二叉树(AVL)的正确种植方法

《算法(java)》                           — — Robert Sedgewick, Kevin Wayne

972
来自专栏尾尾部落

[剑指offer] 二叉树中和为某一值的路径

输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

671
来自专栏日常分享

Java 通过先序中序序列生成二叉树

  二叉树的前序以及后续序列,以空格间隔每个元素,重构二叉树,最后输出二叉树的三种遍历方式的序列以验证。

1291
来自专栏向治洪

ArrayList和LinkedList的区别

一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构...

1919
来自专栏彭湖湾的编程世界

【算法】论平衡二叉树(AVL)的正确种植方法

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

31111
来自专栏JavaEdge

JAVA CalendarCalendar 与 Date 的转换注意的事项:

3875
来自专栏Hongten

日历(Calendar)_java版(某年的日历,某月的日历)_用户完全自定义

========================================================

1762
来自专栏开发与安全

算法:二叉排序树的删除节点策略及其图形化(二叉树查找)

二叉排序树(BST,Binary Sort Tree)具有这样的性质:对于二叉树中的任意节点,如果它有左子树或右子树,则该节点的数据成员大于左子树所有节点的数据...

2129
来自专栏尾尾部落

[剑指offer] 平衡二叉树

遍历每个结点,借助一个获取树深度的递归函数,根据该结点的左右子树高度差判断是否平衡,然后递归地对左右子树进行判断。

823
来自专栏书山有路勤为径

二叉查找树转换为较大树

Leetcode 538 已知一个二叉查找树,将它转换为一个较大树,即所有的二叉查找树的节点,赋值为该节点本身的值与该节点大的节点的值的和

802

扫码关注云+社区