【算法】JZ54 二叉搜索树的第k个节点

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

题解

中序遍历结果是升序的。 把问题转化成，在搜索二叉树中，中序找第k个结点。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
// 法一：递归
// 法二：非递归 --- 栈
class Solution {
          
   
public:
    // 中序遍历，升序系列的第k个数字
    int KthNode(TreeNode* proot, int k) {
          
   
        if(nullptr == proot || k <= 0)
            return -1;
        
        stack<TreeNode*> st;
        TreeNode* node = proot;
        
        do {
          
   
            // 压入左节点
            while(nullptr != node)
            {
          
   
                st.push(node);
                node = node->left;
            }
            // 根
            if(!st.empty())
            {
          
   
                node = st.top();
                st.pop();
                
                k--;
                if(k == 0)
                {
          
   
                    return node->val;
                }
                // 右
                node = node->right;
            }
            
        }while(nullptr != node || !st.empty());
        
        return -1;
    }
};

循环终止条件确定

while(nullptr != node || !st.empty());

1、

(nullptr == node

2、

st.empty()