IT博客汇 | 257. Binary Tree Paths

257. Binary Tree Paths

10k发表于 2023-07-14 00:00:00

Question

Given the root of a binary tree, return all root-to-leaf paths in any order**.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Algorithm

This is a question that binary tree combined with backtracking.

To get the paths, you travel the tree node by node and each time you reach the leaves you stop here and store the path. Otherwise you record the value of the node and append an arrow string "->" and go to its left and right child.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        helper(res, root, String.valueOf(root.val));
        return res;
    }
    
    private void helper(List<String> res, TreeNode root, String temp) {
        if (root.left == null && root.right == null) {
            res.add(temp);
            return;
        }
        if (root.left != null) helper(res, root.left, temp + "->" + String.valueOf(root.left.val));
        if (root.right != null) helper(res, root.right, temp + "->" +  String.valueOf(root.right.val));
    }
}