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

相关文章

来自专栏Micro_awake web

python二叉树递归算法之后序遍历,前序遍历,中序遍历

1 #!/usr/bin/env python 2 # -*- coding: utf-8 -*- 3 # @Date : 2016-11-18 0...

2065
来自专栏趣学算法

数据结构 第11讲 二叉树及其创建

二叉树(Binary Tree)是n(n≥0)个结点所构成的集合,它或为空树(n = 0);或为非空树,对于非空树T:

892
来自专栏开发与安全

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

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

2009
来自专栏尾尾部落

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

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

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

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

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

902
来自专栏Java Edge

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

3145
来自专栏Hongten

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

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

1122
来自专栏Android干货

Python枚举类

Enum可以把一组相关常量定义在一个class中,且class不可变,而且成员可以直接比较。

652
来自专栏武培轩的专栏

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

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

3504
来自专栏WindCoder

DateUtil-常用关于date的工具类备份

621

扫码关注云+社区