发表于 | 分类于

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:

Input:
s: “abab” p: “ab”

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

解法1： 滑动窗口， O（N) Time

比较自然想到的是用一个hash来记录p中出现的字符个数，然后对于每一个字串去比较是否是一个p的anagram。但如果一个一个的字串比较的话，复杂度很高。
仔细想一想，每次向前挪一位的时候，我们只是更新了一个字符的信息，所以说一部分在hashtable中的信息还是可以用的。
那么我们可以运用滑动窗口的算法来保留已经得到的信息，每移动一格就更新一下hashtable中的信息。
具体的算法是这样的：
先遍历一遍p，记录每一个字符出现的次数并记录在hashtable中。
这里用的是滑动窗口的算法。用两个指针记录当前窗口的大小，

  1. right指针不停的向右侧移动。如果right指向的字符出现次数>=1， 则表示找到一个对应的字符，所剩下的字符-1。
  2. right字符在hashtable中出现的次数-1（无论是否出现过， 如果没有出现过，则数值为负值，便于区分是否是p中的字符）
  3. right向右移动
  4. 判断count是否为0， 如果是表明所有的字符都出现过，则left指向的起始点就是一个有效的起始点。
  5. 如果窗口大小已经大于p的大小，那么就需要移动左指针。 首先看left指向的是否出现在p中（一定是》0的），如果是则count++
  6. 无论是否出现过，hash的值+1， 表明这个值已经退回。

C++

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
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if (s.empty() || p.empty() ) {
            return res;
        }
        vector<int> hash(26, 0);
        for (char c : p) {
            hash[c - 'a']+=1;
        }
        int left = 0, right = 0; int count = p.size();
        while (right < s.size()) {
            if (hash[s[right] - 'a'] >= 1) {
                --count;
            }
            hash[s[right] - 'a']-=1;
            ++right;
            if (count == 0) {
                res.push_back(left);
            }
            if (right - left == p.size()) {
                if (hash[s[left] - 'a'] >= 0) {
                    count++;
                }
                hash[s[left] - 'a']+=1;
                left++;
            }
        }
        return res;
    }
};

Java

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
public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<Integer>();
        if (p == null || s == null || p.length() == 0 || s.length() == 0) {
            return res;
        }
        int[] hash = new int[26];
        for (char ss: p.toCharArray()) {
            hash[ss - 'a']++;
        }
        int left = 0, right = 0, count = p.length();
        while (right < s.length()) {
            char cur = s.charAt(right);
            if (hash[cur - 'a'] > 0) {
                count--;
            }
            ++right;
            hash[cur - 'a']--;
            if (count == 0) {
                res.add(left);
            }
            if (right - left == p.length()) {
                if (hash[s.charAt(left) - 'a'] >= 0) {
                    ++count;
                }
                hash[s.charAt(left) - 'a']++;
                ++left;
            }
        }
        return res;
    }
}

运用滑动窗口的模板写一下
Java

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
public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<Integer>();
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : p.toCharArray()) {
            map.put(c, map.getOrDefault(c,0) + 1);
        }
        int start = 0, end = 0;
        int count = map.size();
        while (end < s.length()) {
            char current = s.charAt(end);
            if (map.containsKey(current)) {
                map.put(current, map.get(current) - 1);
                if (map.get(current) == 0) {
                    count--;
                }
            }
            end++;
            while (count == 0) {
                // check if the current substring (start, end) qualify for a anagram
                if (end - start == p.length()) {
                    res.add(start);
                }
                char temp = s.charAt(start);
                if (map.containsKey(temp)) {
                    map.put(temp, map.get(temp) + 1);
                    if (map.get(temp) > 0) {
                        count++;
                    }
                }
                start++;
            }
        }
        return res;
    }
}

发表于 | 分类于

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given “egg”, “add”, return true.

Given “foo”, “bar”, return false.

Given “paper”, “title”, return true.

Note:
You may assume both s and t have the same length.

解法1：

用hashmap， 要注意的是，除了有aa->ab情况要排除，还有ab->aa的情况也要排除，所以这里用到了两个hashmap。
C++
C++里hashmap查看是否有key也可以用map.count(key)

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
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }
        if (s.empty()) {
            return true;
        }
        
        unordered_map<char, char> mapLeft;
        unordered_map<char, char> mapRight;
        for (int i = 0; i < s.size(); ++i) {
            auto left2Right = mapLeft.find(s[i]);
            auto right2Left = mapRight.find(t[i]);
            if (left2Right == mapLeft.end() && right2Left == mapRight.end()) {
                mapLeft[s[i]] = t[i];
                mapRight[t[i]] = s[i];
            } else if (left2Right != mapLeft.end()) {
                if (mapLeft[s[i]] != t[i]) {
                    return false;
                }
                mapRight[t[i]] = s[i];
            } else if (right2Left != mapRight.end()) {
                if (mapRight[t[i]] != s[i]) {
                    return false;
                }
                mapLeft[s[i]] = t[i];
            } else if (mapLeft[s[i]] != t[i] || mapRight[t[i]] != s[i]) {
                return false;
            }
        }
        
        return true;
    }
};

Java

1

发表于 | 分类于

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6

解法1： Divide & Conquer

思路是对于每一个节点，如果有left和right两个child, 对left和right分别做flatten的话，只需要把left的child和right的root相连，同时把left的root设为NULL. 然后把root和left的root相连就得到了flatten的list。
具体实现起来的时候，可以建立一个辅助的struct来存储每一个节点对应的flatten之后的root和child。
C++

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct NodePair {
  TreeNode* root;
  TreeNode* child;
  NodePair(TreeNode* r, TreeNode* c):root(r),child(c) {}
};
class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) {
            return;
        }
        NodePair res = helper(root);
    }
        NodePair helper(TreeNode* root) {
        if (!root) {
            return NodePair(NULL, NULL);
        }
        if (!root->left && !root->right) {
            return NodePair(root, root);
        }
        NodePair left = helper(root->left);
        NodePair right = helper(root->right);
        // Combine
        root->left = NULL;
        if (!left.root) {
            root->right = right.root;
        } else {
            root->right = left.root;
            left.child->left = NULL;
            left.child->right = right.root;
        }
        return NodePair(root, right.child?right.child:left.child);
    }
};

Java

1

解法2： Preorder traversal

从给的例子可以看到，最后的顺序是一个preorder traversal。 那么我们可以先进行preorder， 然后把vector中的node都连接起来。
C++

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
class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) {
            return;
        }
        vector<TreeNode*> nodes;
        preorder(nodes, root);
        for (int i = 0; i < nodes.size() - 1; ++i) {
            nodes[i]->left = NULL;
            nodes[i]->right = nodes[i + 1];
        }
        nodes[nodes.size() - 1]->left = nodes[nodes.size() - 1]->right = NULL;
        return;
    }
    void preorder(vector<TreeNode*>& nodes, TreeNode* root) {
        if (!root) {
            return;
        }
        nodes.push_back(root);
        preorder(nodes, root->left);
        preorder(nodes, root->right);
    }
};

解法3： Iterative

基本思想就是从上往下，如果有left child就把最右端的接到right child上，然后把left child移到左边。然后再按照路劲往下一个node，也就是说root = root.right

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        while (root != null) {
            if (root.left != null) {
                TreeNode prev = root.left;
                while (prev.right != null) {
                    prev = prev.right;
                }
                prev.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;  // go down along the path
        }
    }
}

发表于 | 分类于

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

解法1： O（M + N）， O（1） Space

本题的function的return是void，看来必须是inplace的。 由于两个array都是sorted， 我们可以从大到小的merge，这样我们可以把merge过的数值插入到第一个array的尾部。
用一个指针维护插入的位置，另两个指针从大到小遍历两个array。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        
        int mp = m - 1;
        int np = n - 1;
        int i = nums1.size() - 1;
        while (mp >= 0 && np >= 0) {
            if (nums1[mp] >= nums2[np]) {
                nums1[i--] = nums1[mp--];
            }else {
                nums1[i--] = nums2[np--];
            }
        }
        while (mp >= 0) {
            nums1[i--] = nums1[mp--];
        }
        while (np >= 0) {
            nums1[i--] = nums2[np--];
        }
        
    }
};

Java

1

发表于 | 分类于

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

解法1： DFS

很直白的一个DFS的题目，用递归的方式很简洁的完成。基本思路是对每一个子节点，都可以看成是一个新的问题，只是问题变成了要求的sum是sum-root->val。
直到leaf的时候判断当前要求的sum和自己是否一致（或者是更新了的sum是否为0）
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) {
            return false;
        }
        
        int cur = sum - root->val;
        if (!root->left && !root->right) {
            return cur == 0;
        }
        
        return hasPathSum(root->left, cur) || hasPathSum(root->right, cur);
    }
};

Java

1

发表于 | 分类于

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

1

/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Hide Tags Tree Depth-first Search
Show Similar Problems

解法1： DFS ， O(N) Space + O（N） Time

题意是对每一个path做一个操作（记录成一个数字），容易想到用DFS来遍历整棵数。
遍历的时候用一个vector存储每一个数字，最后对vector求一下和。
C++

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
/**
 * 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 sumNumbers(TreeNode* root) {
        if (!root) {
            return 0;
        }
        
        vector<int> temp;
        helper(root, temp, 0);
        int sum = 0;
        for (int i = 0; i < temp.size(); ++i) {
            sum += temp[i];
        }
        return sum;
    }
    
    void helper(TreeNode* root, vector<int>& buf, int cur) {
        if (!root) {
            return;
        }
        
        cur = cur * 10 + root->val;
        if (!root->left && !root->right) {
            buf.push_back(cur);
            return;
        }
        
        helper(root->left, buf, cur);
        helper(root->right, buf, cur);
    }
};

Java

1

解法2： DFS ， O(1) Space + O（N） Time

实际上不需要用一个vector来存储见到的数字。
C++

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
/**
 * 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 sumNumbers(TreeNode* root) {
        if (!root) {
            return 0;
        }
        
        return helper(root, 0);
       
    }
    
    int helper(TreeNode* root, int cur) {
        if (!root) {
            return 0;
        }
        
        cur = cur * 10 + root->val;
        if (!root->left && !root->right) {
            return cur;
        }
        
        int sum = helper(root->left, cur) + helper(root->right, cur);
        return sum; 
    }
    
};

发表于 | 分类于

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example:
n = 10, I pick 6.

Return 6.

解法1： Binary Search O（logn)

很典型的二分法的题目。 没有难点。
C++

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
// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);
class Solution {
public:
    int guessNumber(int n) {
        
        int start = 1, end = n;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (guess(mid) <0 ) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        if (guess(end) == 0) {
            return end;
        }
        
        return start;
    }
};

Java

1

发表于 | 分类于

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

解法1： O（N N） Time + O(NN) Space, 一次遍历

本题要满足三个条件，行，列以及小方块都不能包含重复的数字。
可以用三个数组记录每一个条件是否满足，因为每个条件有9行，9列或者9个小方块。 每一个条件能出现的数字只有1到9。
那么每次扫描一个数字时，判断三个条件是否出现过一样的数字，如果有则返回false。
这样的做法好处是只需要遍历一次，代码很整洁。
要注意的是在计算小方块的index的时候， 用了k = i / 3 3 + j / 3, 注意这里因为i是int，所以不能把/33抵消掉。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
       
       bool rule1[9][9] = {false}, rule2[9][9] = {false}, rule3[9][9] = {false};
       
       for (int i = 0; i < board.size(); ++i) {
           for (int j = 0; j < board[0].size(); ++j) {
               if (board[i][j] != '.') {
                   int digit = board[i][j] - '0' - 1;
                   int smallMatrixIndex = i / 3 * 3 + j / 3;
                   if (rule1[i][digit] || rule2[j][digit] || rule3[smallMatrixIndex][digit]) {
                       return false;
                   }
                   rule1[i][digit] = rule2[j][digit] = rule3[smallMatrixIndex][digit] = true;
               }
           }
       }
       
       return true;
    }
};

Java

1

解1法2： O（N * N） Time + O(1) Space， 三次遍历

C++

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
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        
        unordered_map<int, int> map;
        // check row
        for (int i = 0; i < board.size(); ++i) {
            map.clear();
            for (int j = 0; j < board[i].size(); ++j) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (map[board[i][j]] != 0) {
                    return false;
                }
                map[board[i][j]] = 1;
            }
        }
        
        // check col
        int row = board.size();
        int col = board[0].size();
        for (int i = 0; i < col; ++i) {
            map.clear();
            for (int j = 0; j < row; ++j) {
                if (board[j][i] == '.') {
                    continue;
                }
                if (map[board[j][i]] != 0) {
                    return false;
                }
                map[board[j][i]] = 1;
            }
        }
        
        // check small matrix
        for (int i = 0; i < row / 3; ++i) {
            for (int j = 0; j < col / 3; ++j) {
                map.clear();
                for (int k = i * 3; k < i * 3 + 3; ++k) {
                    for (int m = j * 3; m < j * 3 + 3; ++m) {
                        if (board[k][m] == '.') {
                            continue;
                        }
                        if (map[board[k][m]] != 0) {
                            return false;
                        }
                        map[board[k][m]] = 1;
                    }
                }
            }
        }
        
        return true;
        
    }
};

Java

1

发表于 | 分类于

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Show Company Tags
Show Tags
Show Similar Problems

解法1： Recursion

用递归的in-order很简单，按字面理解就是先左再自己再右。
C++

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
/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        helper(root, res);
        return res;
    }
    void helper(TreeNode* root, vector<int>& res) {
        if (!root) {
            return;
        }
        helper(root->left, res);
        res.push_back(root->val);
        helper(root->right, res);
    }
};

Java

1

解法2： Iterative

主要考虑的就是用一个stack来存储还没有访问的节点， 难点在于确定什么时候push和pop。
那么在寻找最小值的时候，一路上碰到的所有node都push
如果碰到了空节点，则证明现在的这条路已经到底了，需要往回寻找，这个时候就可以pop了，记录节点的数值。并且把将要探寻的指针放到right上继续。
C++

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
/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        stack<TreeNode*> store;
        TreeNode* cur = root;
        while (cur || !store.empty()) {
            if (cur) {
                store.push(cur);
                cur = cur->left;
            } else {
                TreeNode* temp = store.top();
                res.push_back(temp->val);
                store.pop();
                cur = temp->right;
            }
        }
        return res;
    }
};

Java

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        while (root!= null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode temp = stack.pop();
                res.add(temp.val);
                root = temp.right;
            }
        }
        return res;
    }
}

发表于 | 分类于

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Hint:

Try to utilize the property of a BST.
What if you could modify the BST node’s structure?
The optimal runtime complexity is O(height of BST).

解法1： In-order traversal O（N）， N is number of elements

这题可以看成是一个in-order traversal的直接应用，因为BST的in-order traversal是一个有序数组，那么我们就可以根据这个性质，对数进行遍历直到找到第k个node。
C++

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
/**
 * 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) {
        // implement a in-order-traversal
        int count = 0;
        int res;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        while (cur || !s.empty()) {
            if (cur) {
                s.push(cur);
                cur = cur->left;
            } else {
                ++count;
                TreeNode* temp = s.top();
                s.pop();
                if (count == k) {
                    res = temp->val;
                    break;
                }
                cur = temp->right;
            }
        }
        return res;
    }
};

Java

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // in-order traversal iterative solution
        Stack<TreeNode> stack = new Stack<TreeNode>();        
        TreeNode current = root;
        int count = 0;
        int val = 0;
        while ( current != null || !stack.isEmpty()) {
            if (current != null) {
                stack.push(current);
                current = current.left;                
            } else {
                TreeNode temp = stack.pop();
                val = temp.val;
                count++;
                current = temp.right;
                if (count == k) {
                    return val;
                }
            }
        }
        return val;
    }
}

Follow up : O(logN)

参考这篇文章的思路
如果可以修改每一个tree的node的结构，而使其保存leftcount和totalcount。那么一开始建立树需要O(N)的时间，而之后每一次insert和查找则只需要O(logN)的时间。

lang: java
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
class Solution {
    class SuperNode {
        int val;
        int count;
        int total;
        SuperNode left;
        SuperNode right;
        public SuperNode(int val) {
            this.val = val;
            count = 0;
            total = 1;
            left = null;
            right = null;
        }
    };
    public SuperNode build(TreeNode root) {
        if (root == null) return null;
        SuperNode superRoot = new SuperNode(root.val);
        SuperNode left = build(root.left);
        SuperNode right = build(root.right);
        superRoot.left = left;
        superRoot.right = right;
        if (left != null) {
            superRoot.count = left.total;
        } else {
            superRoot.count = 0;
        }
        superRoot.total += ((left == null ? 0 : left.total) + (right == null ? 0 : right.total));
        return superRoot;
    }
    public int kthSmallest(TreeNode root, int k) {
        SuperNode superRoot = build(root);
        return kth(superRoot, k);
    }
    private int kth(SuperNode root, int k) {
        if (root == null || k <= 0) {
            return 0;
        }        
        if (k == root.count + 1) {
            return root.val;
        } else if (k < root.count + 1) {
            return kth(root.left, k);
        } else {
            return kth(root.right, k - root.count - 1);
        }
    }
}