欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

257二叉树的所有路径

程序员文章站 2022-05-20 19:25:05
...

题目描述

给定一个二叉树,返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输出: [“1->2->5”, “1->3”]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

思路分析

递归终止的条件是什么?一次递归中要进行什么操作?递归想要返回什么信息?

基于前序递归模板。

终止条件:节点为空

递归中操作:为叶节点时,将路径加入list,不为叶节点就把此节点的值入str

提交初版代码后发现执行用时13ms…所以将String换成StringBuffer,SB需要进行回溯处理。

代码实现

    /**
     * 直接用string做传递
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        process2(root, list, "");
        return list;
    }

    public static void process2(TreeNode root, List<String> list, String str) {
        if (root == null) {
            return;
        }

        if (root.left == null && root.right == null) {
            str = str + "" + root.val;
            list.add(str);
        } else {
            str = str + root.val + "->";
        }

        process2(root.left, list, str);
        process2(root.right, list, str);
    }


    /**
     * stringbuffer做传递
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths1(TreeNode root) {
        List<String> list = new ArrayList<>();
        process1(root, list, new StringBuffer());
        return list;
    }

    public static void process1(TreeNode root, List<String> list, StringBuffer str) {
        if (root == null) {
            return;
        }
        str.append(root.val);

        if (root.left == null && root.right == null) {
            list.add(str.toString());
        } else {
            if (root.left != null) {
                str.append("->");
                process1(root.left, list, str);
                str.delete(str.lastIndexOf("->"), str.length());
            }
            if (root.right != null) {
                str.append("->");
                process1(root.right, list, str);
                str.delete(str.lastIndexOf("->"), str.length());
            }
        }

    }