给定一棵结点数为n 二叉搜索树,请找出其中的第 k 小的TreeNode结点值。 1.返回第k小的节点值即可 2.不能查找的情况,如二叉树为空,则返回-1,或者k大于n等等,也返回-1 3.保证n个节点的值不一样。
请问为什么“ if(k==0) ans= proot->val;
if(k>0)dfs(proot->right, k);”
这两行代码顺序改变会导致错误
因为如果顺序改变,递归回到祖先节点的时候,虽不会执行if(k>0)dfs(proot->right, k);但却会执行if(k==0) ans= proot->val;导致答案被覆写。
/
* struct TreeNode {
* int val;
* struct TreeNode left;
* struct TreeNode right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param proot TreeNode类
* @param k int整型
* @return int整型
/
int ans=0;
int KthNode(TreeNode* proot, int k) {
// write code here
dfs(proot,k);
return ans;
}
void dfs(TreeNode *proot, int &k){
if(!proot) return;
dfs(proot->left, k);
k--;
cout<<"K:"<<k<<" node:"<<proot->val<<endl;
cout<<ans<<endl;
if(k==0) ans= proot->val;
if(k>0)dfs(proot->right, k);
// if(k==0) ans= proot->val;
}
};