首页 > 代码库 > 4.在二元树中找出和为某一值的所有路径

4.在二元树中找出和为某一值的所有路径

2024-07-05 07:29:27   229人阅读

http://zhedahht.blog.163.com/blog/static/254111742007228357325/

http://www.cnblogs.com/qi09/archive/2011/05/24/2055643.html

题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。

例如输入整数22和如下二元树

                                            10
                                           /   \
                                          5     12
                                        /   \   
                                     　4     7 

则打印出两条路径：10, 12和10, 5, 7。

思路：

1、当访问到某一节点时，把该结点的值添加到当前和变量，且把该结点压入栈中。

2、若结点为叶子结点，且当前和变量==期望的和，则打印栈中的结点值，即为所需的路径。

3、若结点不是叶子结点，继续访问它的左孩子结点，访问它的右孩子结点。

4、删除该结点。包括从当前和变量中减去结点值，从栈中弹出结点值。此时，已回到父结点。

程序中的栈，利用STL中的vector，这样简化了编码工作。

///////////////////////////////////////////////////////////////////////
// Find paths whose sum equal to expected sum
///////////////////////////////////////////////////////////////////////
void FindPath
    (
    BinaryTreeNode*   pTreeNode,    // a node of binary tree
    int               expectedSum,  // the expected sum
    std::vector<int>& path,         // a path from root to current node
    int&              currentSum    // the sum of path
    )
{
    if(!pTreeNode)
        return;

    currentSum += pTreeNode->m_nValue;
    path.push_back(pTreeNode->m_nValue);

    // if the node is a leaf, and the sum is same as pre-defined, 
    // the path is what we want. print the path
    bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);
    if(currentSum == expectedSum && isLeaf)
    {    
        std::vector<int>::iterator iter = path.begin();
        for(; iter != path.end(); ++ iter)
            std::cout << *iter << ‘\t‘;
        std::cout << std::endl;
    }

    // if the node is not a leaf, goto its children
    if(pTreeNode->m_pLeft)
        FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
    if(pTreeNode->m_pRight)
        FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);

    // when we finish visiting a node and return to its parent node,
    // we should delete this node from the path and 
    // minus the node‘s value from the current sum
    currentSum -= pTreeNode->m_nValue;
    path.pop_back();
} 

void FindPath(
    BinaryTreeNode*   pTreeNode,    // a node of binary tree
    int               expectedSum  // the expected sum
    )
{
    int curSum = 0;
    std::vector<int> path;
    FindPath(pTreeNode,expectedSum,path,curSum);
}

 

 


联系
我们