美文网首页
Leetcode 精选之搜索(二叉树的所有路径)

Leetcode 精选之搜索(二叉树的所有路径)

作者: Kevin_小飞象 | 来源:发表于2020-04-03 14:30 被阅读0次

    题目描述

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

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

    示例:

    输入:

       1
     /   \
    2     3
     \
      5
    
    输出: ["1->2->5", "1->3"]
    
    解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
    

    题目链接:力扣

    解题思路

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> paths = new ArrayList<>();
            if (root == null) {
                return paths;
            }
            List<Integer> values = new ArrayList<>();
            backtracking(root, values, paths);
            return paths;
        }
    
        private void backtracking(TreeNode node, List<Integer> values, List<String> paths) {
            if (node == null) {
                return;
            }
            values.add(node.val);
            if (isLeaf(node)) {
                paths.add(buildPath(values));
            } else {
                backtracking(node.left, values, paths);
                backtracking(node.right, values, paths);
            }
            values.remove(values.size() - 1);
        }
    
        private boolean isLeaf(TreeNode node) {
            return node.left == null && node.right == null;
        }
    
        private String buildPath(List<Integer> values) {
            StringBuilder str = new StringBuilder();
            for (int i = 0; i < values.size(); i++) {
                str.append(values.get(i));
                if (i != values.size() - 1) {
                    str.append("->");
                }
            }
            return str.toString();
        }
    }
    

    测试结果

    image.png

    相关文章

      网友评论

          本文标题:Leetcode 精选之搜索(二叉树的所有路径)

          本文链接:https://www.haomeiwen.com/subject/fzmhphtx.html