题解 | #二叉树遍历#

二叉树遍历

https://www.nowcoder.com/practice/6e732a9632bc4d12b442469aed7fe9ce

递归建树,子树为空返回NULL

#include <iostream>
using namespace std;
struct treeNode {
    char letter;
    treeNode* leftChild;
    treeNode* rightChild;
    treeNode(char c) {
        letter = c;
        leftChild = NULL;
        rightChild = NULL;
    }
};
treeNode* buildTree(string preOrderStr, string inOrderStr) {
    if (preOrderStr.size() == 0) {
        return NULL;
    }
    treeNode* newNode = new treeNode(preOrderStr[0]);

    int pos = inOrderStr.find(preOrderStr[0]);
    newNode->leftChild = buildTree(preOrderStr.substr(1, pos), inOrderStr.substr(0,
                                   pos));
    newNode->rightChild = buildTree(preOrderStr.substr(pos + 1),
                                    inOrderStr.substr(pos + 1));
    return newNode;
}
void postOrder(treeNode* root) {
    if (root == NULL) return;
    postOrder(root->leftChild);
    postOrder(root->rightChild);
    cout << root->letter;
}
int main() {
    string a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        treeNode* tree = buildTree(a, b);
        postOrder(tree);
        cout <<  endl;
    }
}
// 64 位输出请用 printf("%lld")

全部评论

相关推荐

06-18 08:36
湖南大学 Java
运营你豪哥:没啥拷打的 1.增加量化结果,现在有点缺效果数据 2.突出复杂性,现在的项目描述有点像功能清单,强调一下技术难点和解决方案。
不给转正的实习,你还去吗
点赞 评论 收藏
分享
06-02 15:17
门头沟学院 Java
心爱的idea:怎么会呢 应该是打招呼有问题 问就说实习6个月全国可飞随时到岗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务