Q:輸入一顆二叉樹和一個整數,打印出二叉樹中結點和為輸入整數的所有路徑。從樹的根結點開始到葉子節點所經過的結點形成一條路徑。結點定義如下:
struct BinaryTreeNode { int m_nValue; BinaryTreeNode *m_pLeft; BinaryTreeNode *m_pRight; }
我們很自然的想到二叉樹的三種遍歷,以先根(前序)遍歷來說,其遍歷的遞歸模板是:
void PreOrder(BinaryTreeNode *root) { if(!root) return; visit(root); PreOrder(root->m_pLeft); PreOrder(root->m_pRight); }真對不同的要求visit()可以做不同的處理,這裡的要求是判斷當前的結點和是否等於給定的值,同時形成了一條路徑(為葉子結點),若是,則輸出這條路徑。
void FindPath(BinaryTreeNode *pRoot, int expecteSum, int curSum) { if(!pRoot) return; curSum += pRoot->m_nValue; path.push_back(pRoot); if(curSum == expecteSum && IsLeaf(pRoot)) { std::vector::iterator iter = path.begin(); while (iter != path.end()) { std::cout << (*iter)->m_nValue << " "; ++iter; } std::cout << std::endl; } if(pRoot->m_pLeft) FindPath(pRoot->m_pLeft,expecteSum,curSum); if(pRoot->m_pRight) FindPath(pRoot->m_pRight,expecteSum,curSum); path.pop_back(); }