C#LeetCode刷题之#257-二叉树的所有路径（Binary Tree Paths）

问题

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

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

输入:

1

/ \

2 3

\

5

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

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

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Input:

1

/ \

2 3

\

5

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

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

示例

public class Program {

    public static void Main(string[] args) {

        var root = new TreeNode(1) {

            left = new TreeNode(2) {

                right = new TreeNode(5)

            },

            right = new TreeNode(3)

        };

        var res = BinaryTreePaths(root);

        ShowArray(res);

        root.right.right = new TreeNode(4);

        res = BinaryTreePaths2(root);

        ShowArray(res);

        Console.ReadKey();

    }

    private static void ShowArray(IList<string> array) {

        foreach(var num in array) {

            Console.Write($"{num} ");

        }

        Console.WriteLine();

    }

    public static IList<string> BinaryTreePaths(TreeNode root) {

        var list = new List<string>();

        if(root != null) {

            var left = BinaryTreePaths(root.left);

            var right = BinaryTreePaths(root.right);

            var current = root.val.ToString();

            if(left.Count == 0 && right.Count == 0) {

                list.Add(current);

            } else {

                if(left.Count != 0) {

                    foreach(var str in left) {

                        list.Add(current + "->" + str);

                    }

                }

                if(right.Count != 0) {

                    foreach(var str in right) {

                        list.Add(current + "->" + str);

                    }

                }

            }

        }

        return list;

    }

    public static IList<string> BinaryTreePaths2(TreeNode root) {

        var res = new List<string>();

        if(root == null) return res;

        TreePaths(res, root, root.val + "");

        return res;

    }

    public static void TreePaths(IList<string> res, TreeNode root, string path) {

        if(root.left == null && root.right == null)

            //若左右子节点都为空，本次路径结束，直接添加到 List

            res.Add(path);

        if(root.left != null)

            //若左子节点不为空，则将左子节点拼接之后参与下次递归

            TreePaths(res, root.left, path + "->" + root.left.val);

        if(root.right != null)

            //若右子节点不为空，则将右子节点拼接之后参与下次递归

            TreePaths(res, root.right, path + "->" + root.right.val);

    }

    public class TreeNode {

        public int val;

        public TreeNode left;

        public TreeNode right;

        public TreeNode(int x) { val = x; }

    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

1->2->5 1->3

1->2->5 1->3->4

分析：

显而易见，以上2种算法的时间复杂度均为： $O(n)$ 。

巴特西

C#LeetCode刷题之#257-二叉树的所有路径（Binary Tree Paths）

最新文章

热门文章