257. Binary Tree Paths

leetcode easy

#csharp#easy#leetcode#recursion#string#tree#two-pointers

Task

Дано корневое дерево, верните все пути от корня до листа в любом порядке.

Лист — это узел без детей.

Пример:

Input: root = [1,2,3,null,5]

Output: ["1->2->5","1->3"]

C# solution

matched/original

public class Solution {
    public void ConstructPaths(TreeNode root, string path, IList<string> paths) {
        if (root != null) {
            path += root.val;
            if (root.left == null && root.right == null) {
                paths.Add(path);
            } else {
                path += "->";
                ConstructPaths(root.left, path, paths);
                ConstructPaths(root.right, path, paths);
            }
        }
    }
    public IList<string> BinaryTreePaths(TreeNode root) {
        IList<string> paths = new List<string>();
        ConstructPaths(root, "", paths);
        return paths;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public void ConstructPaths(TreeNode root, string path, vector<string> paths) {
        if (root != null) {
            path += root.val;
            if (root.left == null && root.right == null) {
                paths.push_back(path);
            } else {
                path += "->";
                ConstructPaths(root.left, path, paths);
                ConstructPaths(root.right, path, paths);
            }
        }
    }
    public vector<string> BinaryTreePaths(TreeNode root) {
        vector<string> paths = new List<string>();
        ConstructPaths(root, "", paths);
        return paths;
    }
}

Java solution

matched/original

class Solution {
    public void construct_paths(TreeNode root, String path, LinkedList<String> paths) {
        if (root != null) {
            path += Integer.toString(root.val);
            if (root.left == null && root.right == null) {
                paths.add(path);
            } else {
                path += "->";
                construct_paths(root.left, path, paths);
                construct_paths(root.right, path, paths);
            }
        }
    }

    public List<String> binaryTreePaths(TreeNode root) {
        LinkedList<String> paths = new LinkedList<>();
        construct_paths(root, "", paths);
        return paths;
    }
}

JavaScript solution

matched/original

class Solution {
    constructPaths(root, path, paths) {
        if (root !== null) {
            path += root.val
            if (root.left === null && root.right === null) {
                paths.push(path)
            } else {
                path += "->"
                this.constructPaths(root.left, path, paths)
                this.constructPaths(root.right, path, paths)
            }
        }
    }

    binaryTreePaths(root) {
        const paths = []
        this.constructPaths(root, "", paths)
        return paths
    }
}

Python solution

matched/original

class Solution:
    def construct_paths(self, root: TreeNode, path: str, paths: List[str]):
        if root:
            path += str(root.val)
            if not root.left and not root.right:
                paths.append(path)
            else:
                path += "->"
                self.construct_paths(root.left, path, paths)
                self.construct_paths(root.right, path, paths)

    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        paths = []
        self.construct_paths(root, "", paths)
        return paths

Go solution

matched/original

func constructPaths(root *TreeNode, path string, paths *[]string) {
    if root != nil {
        path += fmt.Sprintf("%d", root.Val)
        if root.Left == nil && root.Right == nil {
            *paths = append(*paths, path)
        } else {
            path += "->"
            constructPaths(root.Left, path, paths)
            constructPaths(root.Right, path, paths)
        }
    }
}

func binaryTreePaths(root *TreeNode) []string {
    var paths []string
    constructPaths(root, "", &paths)
    return paths
}

Explanation

Algorithm

1️⃣

Если текущий узел не является null, добавьте его значение к текущему пути.

Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.

Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.

2️⃣

Начните с корневого узла, пустого пути и пустого списка путей.

3️⃣

Верните список всех путей от корня до листа.

😎