Point2OfferCode/34_Path_in_Tree.cpp at master · slientreed/Point2OfferCode · GitHub

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

//
//  Created by mark on 2019/7/12.
//  Copyright © 2019年 mark. All rights reserved.
//

/*
 说明：
 1. 问题：34.找二叉树中和为某一值的路径
 2. 思路：前序遍历，递归实现
         1. 每次访问一个节点，把当前权值求和；
         2. 如果当前节点为叶子节点，且路径中节点值的和刚好等于输入值，当前路径符合要求，打印出来；
         3. 如果不是叶子节点，继续访问其左右叶子节点。（当前节点访问后函数会递归到其父节点，所以在函数退出之前要在路径上删除当前节点并减去当前节点的值）
 */


#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <assert.h>

using namespace std;


struct BinaryTreeNode
{
    int val;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
}TN,*pTN;


void _FindPath(BinaryTreeNode* root, int expectSum, vector<int>& path, int cur_sum);

void FindPath(BinaryTreeNode* root, int expectSum)
{
    if(root == nullptr)
        return;

    vector<int> path;
    int cur_sum = 0;
    _FindPath(root, expectSum, path, cur_sum);
}


void _FindPath(BinaryTreeNode* root, int expectSum, vector<int>& path, int cur_sum)
{

    cur_sum += root->val;
    path.push_back(root->val);

    // 如果是叶子节点，且路径上累加值和等于输入值，打印路径
    bool isLeaf = root->left == nullptr && root->right == nullptr;
    if(isLeaf && cur_sum == expectSum)
    {
        cout << "路径是：";
        vector<int>::iterator iter = path.begin();    // 迭代器打印
        for(; iter != path.end(); ++iter)
            printf("%d\t",*iter);

        cout << endl;
    }

    // 如果不是叶子节点，遍历其子节点
    if(root->left != nullptr)
        _FindPath(root->left, expectSum, path, cur_sum);
    if(root->right != nullptr)
        _FindPath(root->right, expectSum, path, cur_sum);

    // 递归结束，返回到父节点前，在路径path去掉当前节点值（否则后面打印会出现访问过的节点）
    path.pop_back();

}


//辅助函数 ------------------------------------------------------------------------------------------------------------------------

// 构建树节点
BinaryTreeNode* CreateTreeNode(int val)
{
    BinaryTreeNode* pNode = new BinaryTreeNode();
    pNode->val = val;
    pNode->left = nullptr;
    pNode->right = nullptr;

    return pNode;
}

// 连接树节点
void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
{
    if(pParent != nullptr)
    {
        pParent->left = pLeft;
        pParent->right = pRight;
    }
}


// 销毁树
void DestroyTree(BinaryTreeNode* root)
{
    if(root != nullptr)
    {
        BinaryTreeNode* left = root->left;
        BinaryTreeNode* right = root->right;

        delete root;
        root = nullptr;

        DestroyTree(left);
        DestroyTree(right);
    }
}

// 先序打印树
void PrintPreOrder(BinaryTreeNode* root)
{
    if(root == nullptr)
        return;

    cout << root->val << " ";
    PrintPreOrder(root->left);
    PrintPreOrder(root->right);

}


int main(){

    BinaryTreeNode* p1 = CreateTreeNode(10);
    BinaryTreeNode* p2 = CreateTreeNode(5);
    BinaryTreeNode* p3 = CreateTreeNode(12);
    BinaryTreeNode* p4 = CreateTreeNode(4);
    BinaryTreeNode* p5 = CreateTreeNode(7);

    ConnectTreeNodes(p1, p2, p3);
    ConnectTreeNodes(p2, p4, p5);

    FindPath(p1, 22);

    return 0;
}