【面试题025】二叉树中和为某一值的路径

【面试题025】二叉树中和为某一值的路径

只有前序遍历，首先访问根结点。

前序遍历访问到某个结点，把该结点添加到路径上，并累加该结点的值，

递归函数推出前，要在路径上删除当前结点，并且减去当前结点的值，

递归返回的条件是到了叶子结点。

保存路径的数据结构实际上就是一个栈。

PathInTree.cpp:

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

#include <iostream>
#include <cstdio>
#include <vector>
#include "BinaryTree.h"

using namespace std;

void FindPath(BinaryTreeNode *pRoot, int expectedSum,
              vector<int> &path, int ¤tSum);

void FindPath(BinaryTreeNode *pRoot, int expectedSum)
{
    if(pRoot == NULL)
        return;

    vector<int> path;
    int currentSum = 0;
    FindPath(pRoot, expectedSum, path, currentSum);
}

void FindPath
(
    BinaryTreeNode   *pRoot,
    int               expectedSum,
    vector<int> &path,
    int              ¤tSum
)
{
    currentSum += pRoot->m_nValue;
    path.push_back(pRoot->m_nValue);

    // 如果是叶结点，并且路径上结点的和等于输入的值
    // 打印出这条路径
    bool isLeaf = pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL;
    if(currentSum == expectedSum && isLeaf)
    {
        printf("A path is found: ");
        vector<int>::iterator iter = path.begin();
        for(; iter != path.end(); ++ iter)
            printf("%d ", *iter);

        printf(" ");
    }

    // 如果不是叶结点，则遍历它的子结点
    if(pRoot->m_pLeft != NULL)
        FindPath(pRoot->m_pLeft, expectedSum, path, currentSum);
    if(pRoot->m_pRight != NULL)
        FindPath(pRoot->m_pRight, expectedSum, path, currentSum);

    // 在返回到父结点之前，在路径上删除当前结点，
    // 并在currentSum中减去当前结点的值
    currentSum -= pRoot->m_nValue;
    path.pop_back();
}

//            10
//         /
//        5        12
//       /
//      4  7
// 有两条路径上的结点和为22
int main()
{
    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);

    BinaryTreeNode *pRoot = pNode10;
    int expectedSum = 22;

    FindPath(pRoot, expectedSum);
    printf(" ");

    DestroyTree(pNode10);
    return 0;
}

BinaryTree.h:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#ifndef _BINARY_TREE_H_
#define _BINARY_TREE_H_

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

BinaryTreeNode *CreateBinaryTreeNode(int value);
void ConnectTreeNodes(
    BinaryTreeNode *pParent,
    BinaryTreeNode *pLeft, BinaryTreeNode *pRight);
void PrintTreeNode(BinaryTreeNode *pNode);
void PrintTree(BinaryTreeNode *pRoot);
void DestroyTree(BinaryTreeNode *pRoot);

#endif /*_BINARY_TREE_H_*/

BinaryTree.cpp:

#include <iostream>
#include <cstdio>
#include "BinaryTree.h"

using namespace std;
BinaryTreeNode *CreateBinaryTreeNode(int value)
{
    BinaryTreeNode *pNode = new BinaryTreeNode();
    pNode->m_nValue = value;
    pNode->m_pLeft = NULL;
    pNode->m_pRight = NULL;

    return pNode;
}

void ConnectTreeNodes(
    BinaryTreeNode *pParent,
    BinaryTreeNode *pLeft,
    BinaryTreeNode *pRight)
{
    if(pParent != NULL)
    {
        pParent->m_pLeft = pLeft;
        pParent->m_pRight = pRight;
    }
}

void PrintTreeNode(BinaryTreeNode *pNode)
{
    if(pNode != NULL)
    {
        printf("value of this node is: %d ", pNode->m_nValue);

        if(pNode->m_pLeft != NULL)
            printf("value of its left child is: %d. ",
                   pNode->m_pLeft->m_nValue);
        else
            printf("left child is null. ");

        if(pNode->m_pRight != NULL)
            printf("value of its right child is: %d. ",
                   pNode->m_pRight->m_nValue);
        else
            printf("right child is null. ");
    }
    else
    {
        printf("this node is null. ");
    }

    printf(" ");
}

void PrintTree(BinaryTreeNode *pRoot)
{
    PrintTreeNode(pRoot);

    if(pRoot != NULL)
    {
        if(pRoot->m_pLeft != NULL)
            PrintTree(pRoot->m_pLeft);

        if(pRoot->m_pRight != NULL)
            PrintTree(pRoot->m_pRight);
    }
}

void DestroyTree(BinaryTreeNode *pRoot)
{
    if(pRoot != NULL)
    {
        BinaryTreeNode *pLeft = pRoot->m_pLeft;
        BinaryTreeNode *pRight = pRoot->m_pRight;

        delete pRoot;
        pRoot = NULL;

        DestroyTree(pLeft);
        DestroyTree(pRight);
    }
}

Makefile:

1
2
3
4
5
6
7
8
9
10
11
12

.PHONY:clean
CPP=g++
CFLAGS=-Wall -g
BIN=test
OBJS=PathInTree.o BinaryTree.o
LIBS=
$(BIN):$(OBJS)
    $(CPP) $(CFLAGS) $^ -o $@ $(LIBS)
%.o:%.cpp
    $(CPP) $(CFLAGS) -c $< -o $@
clean:
    rm -f *.o $(BIN)

运行结果：

A path is found: 10 5 7

A path is found: 10 12