算法1
(dfs void版)
class Solution {
public:
TreeNode ans;
void dfs(TreeNode root, int & k) {
if (!root) return;
dfs(root->left, k);
k–;
if (k == 0) {ans = root; return;}
dfs(root->right, k);
}
TreeNode kthNode(TreeNode root, int k) {
if (!root) return nullptr;
dfs(root, k);
return ans;
}
};
算法2
(dfs 有返回值版)
class Solution {
public:
TreeNode dfs(TreeNode root, int & k) {
if (!root) return nullptr;
auto left = dfs(root->left, k);
k–;
if (k == 0) {return root;}
auto right = dfs(root->right, k);
return left?left:right;
}
TreeNode kthNode(TreeNode root, int k) {
if (!root) return nullptr;
return dfs(root, k);
}
};
解析
无返回值版的比较好写,也容易理解;那么有返回值的时候,应该怎么设置返回值呢?可以看着代码自己思考一下。