二叉树相关问题

//树的子结构：输入两颗二叉树A, B，判断B是不是A的子结构
struct BinaryTreeNode{
    double m_dbValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
bool hasSubTree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2){
    bool result = false;
    if (pRoot1 != nullptr && pRoot2 != nullptr){
        if (Equal(pRoot1->m_dbValue, pRoot2->m_dbValue)){
            result = DoesTree1HaveTree2(pRoot1, pRoot2);
        }
        if (!result){
            result = hasSubTree(pRoot1->m_pLeft, pRoot2);
        }
        if (!result){
            result = hasSubTree(pRoot1->m_pRight, pRoot2);
        }
    }
    return result;
}
bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2){
    if (pRoot1 == nullptr)
        return false;
    if (pRoot2 == nullptr)
        return true;
    if (Equal(pRoot1->m_dbValue, pRoot2->m_dbValue)){
        return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft)
                && DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
    }
    else
        return false;
}
bool Equal(double a, double b){
    return ((a - b) > -0.0000001 && (a - b) < 0.0000001);
}

//二叉树的镜像：输入一颗二叉树， 输出二叉树的镜像
struct BinaryTreeNode{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
void MirrorRecursively(BinaryTreeNode* pRoot){
    if (pRoot == nullptr)
        return;
    if (pRoot->m_pLeft == nullptr && pRoot->m_pRight == nullptr)
        return;
    BinaryTreeNode* pTemp = pRoot->m_pLeft;
    pRoot->m_pLeft = pRoot->m_pRight;
    pRoot->m_pRight = pTemp;
    if (pRoot->m_pLeft){
        MirrorRecursively(pRoot->m_pLeft);
    }
    if (pRoot->m_pRight){
        MirrorRecursively(pRoot->m_pRight);
    }
}

//判断一颗二叉树是否是对称二叉树：二叉树和它的镜像一样，则它是对称的
bool isSymmetrical(BinaryTreeNode* pRoot){
    return isSymmetrical(pRoot, pRoot);
}
bool isSymmetrical(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2){
    if (pRoot1 == nullptr && pRoot2 == nullptr)  //输入空的树，或者到达叶节点
        return true;
    if (pRoot1 == nullptr || pRoot2 == nullptr)  //结构不同
        return false;
    if (pRoot1->m_nValue == pRoot2->m_nValue){   //结构相同但值不同
        return isSymmetrical(pRoot1->m_pLeft, pRoot2->m_pRight)
                && isSymmetrical(pRoot1->m_pRight, pRoot2->m_pLeft);
    }
}

//从上到下打印二叉树,不分行的打印: 使用STL队列实现二叉树的层序遍历（广度优先遍历）
#include <deque>
using namespace std;
struct BinaryTreeNode{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
void printTreeFromTopToBottom(BinaryTreeNode* pRoot){
    if (pRoot == nullptr)
        return;
    std::deque<BinaryTreeNode*> dequeTreeNode;
    dequeTreeNode.push_back(pRoot);
    while (dequeTreeNode.size()){
        BinaryTreeNode* pNode = dequeTreeNode.front();
        dequeTreeNode.pop_front();
        printf("%d", pNode->m_nValue);
        if (pNode->m_pLeft != nullptr)
            dequeTreeNode.push_back(pNode->m_pLeft);
        if (pNode->m_pRight != nullptr)
            dequeTreeNode.push_back(pNode->m_pRight);
    }
}

//从上到下打印二叉树，分行打印： 增加两个变量计数，当前层待打印的节点树，和下一层节点个数
#include <queue>
using namespace std;
void printTree(BinaryTreeNode* pRoot){
    if (pRoot)
        return;
    std::queue<BinaryTreeNode*> queueTreeNode;
    queueTreeNode.push(pRoot);
    int toBePrinted = 1;
    int nextLevel = 0;
    while (queueTreeNode.size()){
        BinaryTreeNode* pNode = queueTreeNode.front();
        queueTreeNode.pop();
        printf("%d", pNode->m_nValue);
        if (pNode->m_pLeft){
            queueTreeNode.push(pNode->m_pLeft);
            ++nextLevel;
        }
        if (pNode->m_pRight){
            queueTreeNode.push(pNode->m_pRight);
            ++nextLevel;
        }
        --toBePrinted;
        if (toBePrinted == 0){
            printf("
");
            toBePrinted = nextLevel;
            nextLevel = 0;
        }
    }
}

//二叉搜索树的后序遍历序列：判断输入的一个数组是不是某二叉搜索树的后序遍历序列
bool VerifySequenceOfBST(int sequence[], int length){
    if (sequence == nullptr || length <= 0)
        return false;
    int rootVal = sequence[length - 1];
    //二叉搜索树中左子树节点的值小于右子树节点值，
    int i = 0;
    for (; i < length - 1; ++i){
        if (sequence[i] > rootVal)
            break;
    }  //最后i为右子树起点数组下标
    //遍历右子树节点值判断是否大于根节点值
    int j = i;
    for (; j < length - 1; ++j){
        if (sequence[j] < rootVal)
            return false;
    }
    //判断左子树是不是二叉搜索树，包含了i = 0即没有左子树时left为true情况
    bool left = true;
    if (i > 0){
        left = VerifySequenceOfBST(sequence, i);
    }
    //判断右子树是不是二叉搜索树，包含了i = length - 1即没有右子树时right为true情况
    bool right = true;
    if (right < length - 1){
        right = VerifySequenceOfBST(sequence + i, length - i - 1);
    }
    return left && right;
}

//二叉树中和为某一值的路径：输入一颗二叉树，和一个整数，打印出二叉树中节点值的和为输入整数的所有路径
void FindPath(BinaryTreeNode* pRoot,int expectedSum){
    if (pRoot == nullptr)
        return;
    int currentSum = 0;
    std::vector<int> path;
    FindPath(pRoot, path, expectedSum, currentSum);
}
void FindPath(BinaryTreeNode* pRoot, std::vector<int>& path, int expectedSum, int currentSum){
    currentSum += pRoot->m_nValue;
    path.push_back(pRoot);
    bool isLeaf = pRoot->m_pLeft == nullptr && pRoot->m_pRight == nullptr;
    if (currentSum == expectedSum && isLeaf){
        std::vector<int>::iterator iter = path.begin();
        for (; iter != path.end(); ++iter){
            printf("%d	", *iter);
        }
        printf("
");
    }
    if (pRoot->m_pLeft != nullptr){
        FindPath(pRoot->m_pLeft, path, expectedSum, currentSum);
    }
    if (pRoot->m_pRight != nullptr){
        FindPath(pRoot->m_pRight, path, expectedSum, currentSum);
    }
    path.pop_back();
}