我写故我在

I write, therefore I am

Posts Tagged ‘Tree’

程序员面试题集004

Posted by ieipi 于 九月 16, 2011

题目
输入一个整数和一颗二元树,打印出与输入整数相等的所有从根节点到叶子节点的路径.
思路
首先根据树的遍历算法很容易找到满足条件的叶子节点.
问题是如何打印出从根节点到该节点的路径?
进一步考虑,遍历通常用的是递归算法,从根节点到叶子节点的函数调用过程系统已经保存好了,用到的数据结构就是栈.
树中遍历的过程即是一个入栈和出栈的过程.所以我们同样可以采用一个栈来显式保存遍历的路径.
源代码
/**
 * @brief find the path whose sum equals the specified number.
 *
 * @param pNode root
 * @param expectedSum expected sum.
 * @param path the stack holds the path.
 * @param currentSum sum of the current path.
 */
    void
FindPath (struct BinaryTreeNode *pNode, int expectedSum, vector &path, int &currentSum  )
{
    if(pNode == NULL) {
        return;
    }
    currentSum += pNode->m_nValue;
    path.push_back(pNode->m_nValue);

    bool isLeaf = (pNode->m_pLeft == NULL)&&(pNode->m_pRight == NULL);
    if(currentSum == expectedSum && isLeaf) {
        vector::iterator itr = path.begin();
        for(; itr != path.end(); itr++) {
            cout << *itr << "\t";
        }
        cout << endl;
    }
    if(pNode->m_pLeft)
        FindPath(pNode->m_pLeft, expectedSum, path, currentSum);
    if(pNode->m_pRight)
        FindPath(pNode->m_pRight, expectedSum, path, currentSum);

    currentSum -= pNode->m_nValue;
    path.pop_back();
    return ;
}		/* -----  end of function FindPath  ----- */

 Reference

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

Posted in 算法, 技术 | Tagged: , | Leave a Comment »