算法之禅-递归01

构造树，并求每条路径和

第一步：构造树节点用到的类：

public class Node{
    public int Val{get;set;}
    public Node? LNode{get;set;}
    public Node? RNode{get;set;}

    public Node(int val)
    {
        this.Val = val;
    }
}

第二步构造树：

public static Node? BuildeTree(int[] arr,int li,int hi)
    {
        if (li > hi) return null;
        int mi = li + ((hi - li) >> 1);
        Node root = new Node(arr[mi]);
        root.LNode = BuildeTree(arr,li,mi-1);
        root.RNode = BuildeTree(arr,mi+1,hi);
        return root;
    }

第三步求路径和：

// 求路径和 递归
    public static Dictionary<int,int> GetSumPath(Node root, int sumQ, Dictionary<int,int> nodeSum)
    {
        // 保护机制
        if (root == null) return null;
        sumQ = sumQ + (root.Val);
            if (root.LNode == null && root.RNode == null) {nodeSum.Add(root.Val,sumQ);sumQ = sumQ - root.Val;}
        GetSumPath(root.LNode,sumQ,nodeSum);
        GetSumPath(root.RNode,sumQ,nodeSum);
        return nodeSum;
    }

运行代码：

int[] arr = {1,2,3,4,5,6,7};
var tree = TreeProject.BuildeTree(arr,0,arr.Length - 1);
var dic = new Dictionary<int,int>();
TreeSum.GetSumPath(tree,0, dic);
foreach(var item in dic)
{
    System.Console.WriteLine(  $"终结点名称：{item.Key} - 路径和：{item.Value } ");
}

学习反思：
1.算法学习还是要画图，只靠脑子想是不行的