二叉树求先序遍历第k个节点，复杂度为树的深度

Question

求主一下，我根据这个代码的逻辑走的话先找先根序列地第一个节点a，但根本找到的却是中序遍历地第一个节点，这个代码错了了吗，还是我错了，希望各位看一下，指点一下我哪里错了

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

你的代码是正确的，但是你应该按照先序遍历的规则进行实现。

以下是完整的代码：

#include<iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    int k = 3;
    int r = root->findRank(k);
    cout << "Rank of the kth node is: " << r << endl;

    delete root;
    return 0;
}

int findRank(TreeNode *root, int k) {
    int leftCount = 0;
    int rightCount = 0;

    if (root == NULL) {
        return -1;
    }

    while (root != NULL && leftCount < k) {
        leftCount++;
        root = root->left;
    }

    while (root != NULL && rightCount < k) {
        rightCount++;
        root = root->right;
    }

    return root ? root->val : -1;
}

在这个版本中，我首先计算了根节点及其所有左子节点和右子节点的数量，然后通过while循环查找第k个结点，并返回其地址。注意在findRank()函数中，我使用了leftCount和rightCount来存储每个结点在左子树或右子树中的数量。最后，如果找到了第k个结点，函数会直接返回该结点的值，否则返回-1。