二叉树从根节点出发的所有路径

二叉树从根节点出发的所有路径

看上图中 二叉树结构
从根节点出发的所有路径 如下
6->4->2->1
6->4->2->3
6->4->5
6->8->7
6->8->9

逻辑思路：
按照先序遍历 加 回溯法 实现

代码如下

        // 调用此方法，将根节点传递进来
        public static IList<IList<int>> Path(BinNode<int> root)
        {
            // 存储所有路径，每一项为一个路径
            List<IList<int>> resultList = new List<IList<int>>();

            List<int> list = new List<int>();
            Path(root, resultList, list);

            // 遍历打印所有路径
            foreach(var listTemp in resultList)
            {
                string msg = "";
                foreach(var item in listTemp)
                {
                    msg += "->" + item;
                }
                Console.WriteLine(msg);
            }

            return resultList;
        }

        public static void Path(BinNode<int> root, IList<IList<int>> resultList, List<int> list)
        {
            if (null == root)
            {
                return;
            }

            list.Add(root.Element);
            // 如果 左子树和右子树 都不存在，则路径结束
            if (null == root.LeftChild && null == root.RightChild)
            {
                List<int> newList = new List<int>(list);
                // 将路径存储
                resultList.Add(newList);
                return;
            }

            if (root.LeftChild != null)
            {
                Path(root.LeftChild, resultList, list);
                // 回溯
                list.RemoveAt(list.Count - 1);
            }

            if (root.RightChild != null)
            {
                Path(root.RightChild, resultList, list);
                // 回溯
                list.RemoveAt(list.Count - 1);
            }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53