// 面试题34：二叉树中和为某一值的路径

// 题目：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所

// 有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

#include <iostream>

#include "BinaryTree.h"

#include <vector>

using namespace std;

void FindPath(BinaryTreeNode* pRoot, int expectedSum, std::vector<int>& path, int& currentSum);

void FindPath(BinaryTreeNode* pRoot, int expectedSum)

{

    if (pRoot == nullptr)

        return;

    std::vector<int> path;

    int currentSum = ;

    FindPath(pRoot, expectedSum, path, currentSum);

}

void FindPath

(

    BinaryTreeNode*   pRoot,

    int               expectedSum,

    std::vector<int>& path,

    int&              currentSum

)

{

    currentSum += pRoot->m_nValue;

    path.push_back(pRoot->m_nValue);

    // 如果是叶结点，并且路径上结点的和等于输入的值

    // 打印出这条路径

    bool isLeaf = (pRoot->m_pLeft == nullptr && pRoot->m_pRight == nullptr);

    if (currentSum == expectedSum && isLeaf)

    {

        printf("A path is found: ");

        vector<int>::iterator iter = path.begin();//使用迭代器而不是下标

        for (; iter != path.end(); ++iter)

            printf("%d\t", *iter);

        printf("\n");

    }

    // 如果不是叶结点，则遍历它的子结点，注意是遍历

    if (pRoot->m_pLeft != nullptr)

        FindPath(pRoot->m_pLeft, expectedSum, path, currentSum);

    if (pRoot->m_pRight != nullptr)

        FindPath(pRoot->m_pRight, expectedSum, path, currentSum);

    // 在返回到父结点之前，在路径上删除当前结点，

    // 并在currentSum中减去当前结点的值

    currentSum -= pRoot->m_nValue;

    path.pop_back();

}

// ====================测试代码====================

void Test(const char* testName, BinaryTreeNode* pRoot, int expectedSum)

{

    if (testName != nullptr)

        printf("%s begins:\n", testName);

    FindPath(pRoot, expectedSum);

    printf("\n");

}

//            10

//         /      \

//        5        12

//       /\

//      4  7

// 有两条路径上的结点和为22

void Test1()

{

    BinaryTreeNode* pNode10 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode12 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode7 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode10, pNode5, pNode12);

    ConnectTreeNodes(pNode5, pNode4, pNode7);

    printf("Two paths should be found in Test1.\n");

    Test("Test1", pNode10, );

    DestroyTree(pNode10);

}

//            10

//         /      \

//        5        12

//       /\

//      4  7

// 没有路径上的结点和为15

void Test2()

{

    BinaryTreeNode* pNode10 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode12 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode7 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode10, pNode5, pNode12);

    ConnectTreeNodes(pNode5, pNode4, pNode7);

    printf("No paths should be found in Test2.\n");

    Test("Test2", pNode10, );

    DestroyTree(pNode10);

}

//               5

//              /

//             4

//            /

//           3

//          /

//         2

//        /

//       1

// 有一条路径上面的结点和为15

void Test3()

{

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode1 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode5, pNode4, nullptr);

    ConnectTreeNodes(pNode4, pNode3, nullptr);

    ConnectTreeNodes(pNode3, pNode2, nullptr);

    ConnectTreeNodes(pNode2, pNode1, nullptr);

    printf("One path should be found in Test3.\n");

    Test("Test3", pNode5, );

    DestroyTree(pNode5);

}

// 1

//  \

//   2

//    \

//     3

//      \

//       4

//        \

//         5

// 没有路径上面的结点和为16

void Test4()

{

    BinaryTreeNode* pNode1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode1, nullptr, pNode2);

    ConnectTreeNodes(pNode2, nullptr, pNode3);

    ConnectTreeNodes(pNode3, nullptr, pNode4);

    ConnectTreeNodes(pNode4, nullptr, pNode5);

    printf("No paths should be found in Test4.\n");

    Test("Test4", pNode1, );

    DestroyTree(pNode1);

}

// 树中只有1个结点

void Test5()

{

    BinaryTreeNode* pNode1 = CreateBinaryTreeNode();

    printf("One path should be found in Test5.\n");

    Test("Test5", pNode1, );

    DestroyTree(pNode1);

}

// 树中没有结点

void Test6()

{

    printf("No paths should be found in Test6.\n");

    Test("Test6", nullptr, );

}

int main(int argc, char* argv[])

{

    Test1();

    Test2();

    Test3();

    Test4();

    Test5();

    Test6();

    system("pause");

    return ;

}