题解 | #二叉树的第K节点#
二叉搜索树的第k个节点
http://www.nowcoder.com/practice/57aa0bab91884a10b5136ca2c087f8ff
1 总结难点
- 基础中序还得反复联系
- C++ stl申明风格和 Java 数据机构申明混淆了，两个stack有质的区别 不然反复报 type conversion错误
http://www.cplusplus.com/reference/stack/stack/push/
请利用好基础代码框架，尤其 非递归的 中序
2 code
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
using namespace std;
//#include <stack>; // std::stack, std::swap(stack)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param proot TreeNode类
* @param k int整型
* @return int整型
*/
int KthNode(TreeNode* proot, int k) {
// write code here
//todo K > treeNodeNumber
if(NULL == proot ){
return -1;
}
//stack<TreeNode*> s = new stack<TreeNode*>();
//stack<TreeNode*> s = new stack<TreeNode*>();
//C++ sytle declaration;
stack<TreeNode*> s;
int i =0;
while( !s.empty() || proot !=NULL ){
if( NULL!= proot){
s.push(proot);
proot = proot->left;
}else{
//已经左到底了
proot = s.top();//get top
s.pop();
//仅仅下面这4行是定制行为
i++;
if( k== i)
{return proot->val;
}
proot = proot->right;
}
}
return -1;
}
};
//参考C++
//https://blog.nowcoder.net/n/465c4a23a0554861a400bce87c2b061b
/**
* 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 count=0;//标记现在是第几个数
vector<int> res;
int KthNode(TreeNode* proot, int k) {
// write code here
if (proot==nullptr||k==0) return -1;
++count;
KthNode(proot->left, k);
res.push_back(proot->val);
//if(count==k) return proot->val;
KthNode(proot->right, k);
return res.size()>=k?res[k-1]:-1;
}
};
//非递归版本
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param proot TreeNode类
* @param k int整型
* @return int整型
*/
public int KthNode (TreeNode proot, int k) {
if(proot == null) return -1;
//中序遍历，第k个节点
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(proot);
TreeNode node = proot;
int i = 0;
while(!stack.isEmpty()){
//遍历node下的所有左节点
while(node.left != null){
stack.push(node.left);
node = node.left;
}
i++;
if(i == k) return stack.pop().val;
TreeNode tmp = stack.pop();
//加入右子树
if(tmp.right != null){
stack.push(tmp.right);
node = tmp.right;
}
}
return -1;
}
}
投递芯原股份等公司10个岗位 >
