剑指offer面试题34:二叉树中和为某一值的路径

小咪咪 2022-03-20 03:18 136阅读 0赞

题目：输入一棵二叉树和一个整数，打印出二叉树中节点值得和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径，二叉树节点的定义如下：

struct Binary TreeNode
    {
      int               m_nValue;
      BinaryTreeNode*   m_pLeft;
      BinaryTreeNode*   m_pRight;
    }

思想：前序遍历符合题意中描述的算法要求，当前序遍历的方式访问到某一节点时，我们把该节点添加到路径上，并累加该节点的值。如果该节点为叶节点，并且路径中节点值得和刚好等于输入的整数，则当前路径符合要求，我们把它打印出来。如果当前节点不是叶节点，则继续访问它的子节点，当前节点访问结束后，递归函数将自动回到它的父节点。因此，我们在函数退出之前要在路径上删除当前节点并减去当前节点的值，以确保返回父节点时路径刚好是从根节点到父节点。我们不难看出保存路径的数据结构实际上是一个栈，因为路径要与递归调用状态一致，而递归调用的本质就是一个压栈和出栈的过程。

代码：

#include<cstdio>
    #include"..\Utilities\BinaryTree.h"
    #include <vector>
    
    void FindPath(BinaryTreeNode* pRoot,int expectedSum,,std::vector<int>& path,int& currentSum);
    void FindPath(BinaryTreeNode* pRoot,int expectedSum)
    {
      if(pRoot==nullpttr)
        return;
    
      std::vector<int>path;
      int currentSum=0;
      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_Right==nullptr;
    if(currentSum==expectedSum && isLeaf)
    {
      printf("A path is found：");
      std::vector<int>::iterator iter= path.begin();
      for(;itrt !=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(char* testName,BinaryTreeNode* pRoot, int expectedSum)
    {
       if(testName !=nullptr)
          print("%s begins:\n",testName);
       FindPath(pRoot,expectedSum);
       
       printf("\n");
    }
    
    
    
    void Test1()
    {
        BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
        BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
        BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12);
        BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
        BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
    
        ConnectTreeNodes(pNode10, pNode5, pNode12);
        ConnectTreeNodes(pNode5, pNode4, pNode7);
    
        printf("Two paths should be found in Test1.\n");
        Test("Test1", pNode10, 22);
    
        DestroyTree(pNode10);
    }
    
    //            10
    //         /      \
    //        5        12
    //       /\        
    //      4  7     
    // 没有路径上的结点和为15
    void Test2()
    {
        BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
        BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
        BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12);
        BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
        BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
    
        ConnectTreeNodes(pNode10, pNode5, pNode12);
        ConnectTreeNodes(pNode5, pNode4, pNode7);
    
        printf("No paths should be found in Test2.\n");
        Test("Test2", pNode10, 15);
    
        DestroyTree(pNode10);
    }
    
    //               5
    //              /
    //             4
    //            /
    //           3
    //          /
    //         2
    //        /
    //       1
    // 有一条路径上面的结点和为15
    void Test3()
    {
        BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
        BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
        BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
        BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
        BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
    
        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, 15);
    
        DestroyTree(pNode5);
    }
    
    // 1
    //  \
    //   2
    //    \
    //     3
    //      \
    //       4
    //        \
    //         5
    // 没有路径上面的结点和为16
    void Test4()
    {
        BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
        BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
        BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
        BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
        BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
    
        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, 16);
    
        DestroyTree(pNode1);
    }
    
    // 树中只有1个结点
    void Test5()
    {
        BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
    
        printf("One path should be found in Test5.\n");
        Test("Test5", pNode1, 1);
    
        DestroyTree(pNode1);
    }
    
    // 树中没有结点
    void Test6()
    {
        printf("No paths should be found in Test6.\n");
        Test("Test6", nullptr, 0);
    }
    
    int main(int argc, char* argv[])
    {
        Test1();
        Test2();
        Test3();
        Test4();
        Test5();
        Test6();
    
        return 0;
    }