博客

//查找二叉树指定节点
bool hasNode(TreeNode* pRoot, TreeNode* pNode){
    if(pRoot == pNode)
        return true;
    bool has = false;
    if(pRoot->lchild != NULL)
        has = hasNode(pRoot->lchild, pNode);
    if(!has && pRoot->rchild != NULL){
        has = hasNode(pRoot->rchild, pNode);
    }
    return has;
}

//利用了后序遍历的思想
//后续搜索每条路径，并将每条路径经过的节点压栈
//当此路径上无要找寻的节点时，将此路径上的节点依次退栈
bool GetNodePath(TreeNode *pRoot, TreeNode *pNode, stack<TreeNode*> &path){
    if(pRoot == pNode)
        return true;
    //不存在此节点
    if(hasNode(pRoot, pNode) == false)
        return false;
    //先将当前节点入栈
    path.push(pRoot);
    bool found = false;
    if(pRoot->lchild != NULL)
        found = GetNodePath(pRoot->lchild, pNode, path);
    if(!found && pRoot->rchild != NULL)
        found = GetNodePath(pRoot->rchild, pNode, path);
    //如果此路径没有找到，出栈
    if(!found)
        path.pop();
    return found;
}