讨论/《中级算法》 - 二叉搜索树中第K小的元素/
《中级算法》 - 二叉搜索树中第K小的元素
共 6 个回复
class Solution {


        public int kthSmallest(TreeNode root, int k) {
            List<Integer> container = new LinkedList<>();
            preOrderSearch(root, container, k);
            return container.get(container.size() - 1);
        }

        void preOrderSearch(TreeNode root, List<Integer> container, int k) {
            if (root.left != null) {
                preOrderSearch(root.left, container, k);
            }
            if (container.size() == k) {
                return;
            }
            container.add(root.val);
            if (root.right != null) {
                preOrderSearch(root.right, container, k);
            }

        }
    }
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int i=1;
        TreeNode* cur=root;
        stack<TreeNode*> mystack={};
        while(!mystack.empty()||NULL!=cur)
        {
            if(cur!=NULL)
            {
                mystack.push(cur);
                cur=cur->left;
            }
            else
            {
                cur=mystack.top();
                mystack.pop();
                if(i++==k){return cur->val;}
                cur=cur->right;
            }
        }
        return 0;
    }
};

谢谢提醒,是中序

JAVA 不使用额外空间递归做法。

class Solution {
    int count=0;
    int ans;
    public int kthSmallest(TreeNode root, int k) {
        preVisit(root, k);
        return ans;
    }
    public void preVisit(TreeNode node, int k){
        if(node == null) return;
        preVisit(node.left, k);
        count++;
        if(count == k){
            ans = node.val;
            return;
        }
        preVisit(node.right, k);
    }
}

是中序遍历

二叉搜索树的前序(不是,是中序)遍历,返回遍历结果的第k个数

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root, vector<int>& result, int k) {
        if (root == nullptr || result.size() >= k) 
            return;
        dfs(root->left, result, k);
        result.push_back(root->val);
        dfs(root->right, result, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> nums;
        dfs(root, nums, k);
        return nums[k-1];
    }
};