
问题
给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
输入:
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
\
5Output: [“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种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4082。