>

LoeiJe

:D 获取中...

何以解忧？唯有暴富

leetcode-230

leetcode 230

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
* 2019:10:28
* leetcode-cn-230
* icenaive
*/

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
/*
* 中序遍历为升序，所以中序遍历一次，存入数组，然后返回第k个就可以
*/
class Solution {
public:
   int kthSmallest(TreeNode* root, int k) {
       if(1 == k) return root->val;
       dfs(root);
       return que[k - 1];
   }
private:
   vector<int> que;
   TreeNode *ans;
   void dfs(TreeNode* root) {
       if(root) {
           dfs(root->left);
           que.push_back(root->val);
           dfs(root->right);
       }
   }
};

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
/*
* 中序遍历 迭代
*/
class Solution {
public:
   int kthSmallest(TreeNode* root, int k) {
       stack<TreeNode *> s;
       vector<int> ans;
       while(!s.empty() || root) {
           while(root){
               s.push(root);
               root = root->left;
           }
           TreeNode *temp = s.top();s.pop();
           ans.push_back(temp->val);
           if(temp->right) root = temp->right;
       }
       return ans[k - 1];
   }
};

// 第k个跳出
class Solution {
public:
   int kthSmallest(TreeNode* root, int k) {
       stack<TreeNode *> s;
       vector<int> ans;
       int res = -1;
       while(!s.empty() || root) {
           while(root){
               s.push(root);
               root = root->left;
           }
           TreeNode *temp = s.top();s.pop();
           k -= 1;
           if(0 == k) {res = temp->val; break;}     // 判断是否是第k个
           //ans.push_back(temp->val);
           if(temp->right) root = temp->right;
       }
       //return ans[k - 1];
        return res;
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 递归到第k个结束
# python 实现的 c++的不会
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        res = None
        def dfs(root):
            nonlocal k, res
            if root.left: dfs(root.left)
            k -= 1
            if 0 == k:
                res = root.val
                return
            if root.right: dfs(root.right)

        dfs(root)
        return res
学习刷题