本篇同步發布於Blog: [解題] LeetCode - 113 Path Sum II

平台：

LeetCode

題號：

113 - Path Sum II

題目連結：

https://leetcode.com/problems/path-sum-ii/

題目說明：

    輸入一個二元樹，再給一個目標和sum，求是否有一條從根節點到葉子節點的路徑，這路徑的值的總和，與sum相等，若相等則記錄此路徑。

解題方法：

　　使用從根節點往子節點深度搜尋，每次累加當前的值總和與路徑，當遇到葉子節點則判斷總和有無與sum相等。

　　須注意edge case根節點是空值的狀況。

難度為Medium

程式碼 (C++ 與 C#)：

#include <iostream>
#include <vector>
using namespace std;

// Definition for a Node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> result;
        if(root == NULL){
            return result;
        }
        
        vector<int> curNodes;
        pathSum(root, sum, 0, curNodes, result);
        return result;
    }
private:
    void pathSum(TreeNode* curNode, int targetSum, int sum, vector<int>& curNodes, vector<vector<int>>& result){
        sum += curNode->val;
        curNodes.push_back(curNode->val);
        if(curNode->left == NULL && curNode->right == NULL && sum == targetSum){
            result.push_back(curNodes);
            return;
        }
        
        if(curNode->left != NULL){
            pathSum(curNode->left, targetSum, sum, curNodes, result);
            curNodes.pop_back();
        }
        
        if(curNode->right != NULL){
            pathSum(curNode->right, targetSum, sum, curNodes, result);
            curNodes.pop_back();
        }
    }
};

int main()
{
	TreeNode node7(7, NULL, NULL);
	TreeNode node8(2, NULL, NULL);
	TreeNode node4(11, &node7, &node8);
	
	TreeNode node2(4, &node4, NULL);
	
	TreeNode node9(5, NULL, NULL);
	TreeNode node10(1, NULL, NULL);
	
	TreeNode node6(4, &node9, &node10);

	TreeNode node5(13, NULL, NULL);
	
    TreeNode node3(8, &node5, &node6);
    TreeNode node1(5, &node2, &node3);
    
    Solution sol;
    vector<vector<int>> result = sol.pathSum(&node1, 22);
	for(int i = 0 ; i < result.size();++i){
		for(int j = 0;j < result[i].size();++j){
			cout << " " << result[i][j];
		}
		cout << endl;
	}

    return 0;
}

using System;
using System.Collections.Generic;

namespace LeetCode113
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public class Solution
    {
        public IList<IList<int>> PathSum(TreeNode root, int sum)
        {
            IList<IList<int>> result = new List<IList<int>>();
            if (root == null)
            {
                return result;
            }

            IList<int> curNodes = new List<int>();
            PathSum(root, sum, 0, curNodes, result);
            return result;
        }

        private void PathSum(TreeNode curNode, int targetSum, int sum, IList<int> curNodes, IList<IList<int>> result)
        {
            sum += curNode.val;
            curNodes.Add(curNode.val);
            if (curNode.left == null && curNode.right == null && sum == targetSum)
            {
                var copyList = new List<int>();
                copyList.AddRange(curNodes);
                result.Add(copyList);
                return;
            }

            if (curNode.left != null)
            {
                PathSum(curNode.left, targetSum, sum, curNodes, result);
                curNodes.RemoveAt(curNodes.Count - 1);
            }

            if (curNode.right != null)
            {
                PathSum(curNode.right, targetSum, sum, curNodes, result);
                curNodes.RemoveAt(curNodes.Count - 1);
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            TreeNode node7 = new TreeNode(7, null, null);
            TreeNode node8 = new TreeNode(2, null, null);
            TreeNode node4 = new TreeNode(11, node7, node8);
            
            TreeNode node2 = new TreeNode(4, node4, null);
            
            TreeNode node9 = new TreeNode(5, null, null);
            TreeNode node10 = new TreeNode(1, null, null);
            
            TreeNode node6 = new TreeNode(4, node9, node10);

            TreeNode node5 = new TreeNode(13, null, null);
            
            TreeNode node3 = new TreeNode(8, node5, node6);
            TreeNode node1 = new TreeNode(5, node2, node3);
            
            Solution sol = new Solution();
            IList<IList<int>> result = sol.PathSum(node1, 22);
            for(int i = 0 ; i < result.Count;++i){
                for(int j = 0;j < result[i].Count;++j){
                    Console.Write(" " + result[i][j]);
                }
                Console.WriteLine();
            }
            Console.ReadKey();
        }
    }
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/100-199/113.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/100-199/113.cs