题解 | #二叉树遍历#

二叉树遍历

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")

全部评论

相关推荐

看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 18:25
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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