编写非递归算法,在二叉树中求位于先序序列中第K个位置的结点。

可以回答这个问题。可以使用栈来实现非递归遍历二叉树，具体步骤如下：

1. 将根节点入栈。
2. 当栈不为空时，弹出栈顶元素，输出该节点的值。
3. 如果该节点有右子树，将右子树入栈。
4. 如果该节点有左子树，将左子树入栈。
5. 重复步骤2-4，直到遍历完整棵树。

在遍历的过程中，可以记录已经遍历过的节点数量，当遍历到第K个节点时，输出该节点的值即可。

相关问题

编写递归算法，在二叉树中求位于先序序列中第k个位置的结点

递归算法如下：

1. 如果树为空，返回空节点。
2. 如果当前节点是第k个节点，返回当前节点。
3. 否则，递归遍历左子树，返回左子树中第k个节点。
4. 如果左子树中没有第k个节点，递归遍历右子树，返回右子树中第k-left-1个节点（left为左子树节点数）。

代码实现如下：

TreeNode* findKthNode(TreeNode* root, int k) {
    if (root == nullptr) {
        return nullptr;
    }
    int leftCount = countNodes(root->left);
    if (leftCount + 1 == k) {
        return root;
    } else if (leftCount >= k) {
        return findKthNode(root->left, k);
    } else {
        return findKthNode(root->right, k - leftCount - 1);
    }
}

int countNodes(TreeNode* root) {
    if (root == nullptr) {
        return ;
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
}

编写递归算法，在二叉树中求位于先序序列中第k个位置的结点。

递归算法实现如下：

1. 如果根节点为空，返回空节点。
2. 如果k等于1，返回根节点。
3. 否则，递归遍历左子树，找到第k-1个节点。
4. 如果左子树中找到了第k-1个节点，返回该节点。
5. 否则，递归遍历右子树，找到第k-1-leftCount个节点。
6. 如果右子树中找到了第k-1-leftCount个节点，返回该节点。
7. 否则，返回空节点。

其中，leftCount表示左子树中的节点数。

代码实现如下：

public TreeNode findKthNode(TreeNode root, int k) {
    if (root == null) {
        return null;
    }
    int leftCount = countNodes(root.left);
    if (k == leftCount + 1) {
        return root;
    } else if (k <= leftCount) {
        return findKthNode(root.left, k);
    } else {
        return findKthNode(root.right, k - leftCount - 1);
    }
}

private int countNodes(TreeNode root) {
    if (root == null) {
        return ;
    }
    return 1 + countNodes(root.left) + countNodes(root.right);
}