二叉树的所有路径(所有从根节点到叶子节点的路径)-257

本篇文章分享二叉树的所有路径(所有从根节点到叶子节点的路径)-257，对你有帮助的话记得收藏一下，看Java资料网收获更多编程知识

题目描述

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。

解题思路

这道题我们采用二叉树里的前序遍历方式，我们要遍历所有到叶子节点的路径，我们采用复用的思想，就是让这里的几个数据结构我们可以重复使用，但是重复使用也就带来数据不一致的情况，我们用一个temp集合来存储遍历路上遇到的元素，但是这里的元素我们肯定是要变化的，你遍历了左叶子节点，那下次你遍历右叶子节点的时候你就要把左叶子节点的值给从我们这个temp集合中去除，所以这里就体现了回溯的思想，一层一层的往上回溯，直到最后回溯的只剩下了根节点，然后再同样的方法去遍历根节点的右子树。

代码实例

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        travel(root, temp, result);
        return result;
    }

    public void travel(TreeNode root, List<Integer> temp, List<String> result) {

        temp.add(root.val);
        if (root.left == null && root.right == null) {
            result.add(zhuanhua(temp));
            return;
        }

        if (root.left != null) {
            travel(root.left, temp, result);
            //这里就是回溯的思想，先让底下的节点一层一层遍历然后回溯去除相应的值，再到这里的根节点就只剩下了根节点，然后就可以去遍历右子树了
            temp.remove(temp.size()- 1);
        }
        
        if (root.right != null) {
            travel(root.right, temp, result);
            temp.remove(temp.size()- 1);
        }
    }
    
    public String zhuanhua(List<Integer> num) {
        String sl = "";
        for (int i = 0; i < num.size(); i++) {
            if (i != num.size() - 1) {
                sl += (num.get(i) + "->");
            } else {
                sl += num.get(i);
            }
        }
        return sl;
    }

}

文章来源:https://www.cnblogs.com/dfj-blog/p/18415430
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！