C++ 递归与非递归方式实现中序遍历
二叉搜索树的第k个结点
http://www.nowcoder.com/questionTerminal/ef068f602dde4d28aab2b210e859150a
用stack实现中序遍历
TreeNode* KthNode(TreeNode* pRoot, int k) { if(pRoot == nullptr || k <= 0) { return nullptr; } vector<TreeNode*> vec; stack<TreeNode*> sta; TreeNode* pNode = pRoot; while(pNode != nullptr || !sta.empty()) { while(pNode != nullptr) { sta.push(pNode); pNode = pNode->left; } if(!sta.empty()) { pNode = sta.top(); sta.pop(); vec.push_back(pNode); pNode = pNode->right; } } int length = vec.size(); if(k <= length) { return vec[k - 1]; } return nullptr;
非递归方式(stack)实现
TreeNode* KthNode(TreeNode* pRoot, int k) { if(pRoot == nullptr || k <= 0) { return nullptr; } vector<TreeNode*> vec; stack<TreeNode*> sta; TreeNode* pNode = pRoot; while(pNode != nullptr || !sta.empty()) { while(pNode != nullptr) { sta.push(pNode); pNode = pNode->left; } if(!sta.empty()) { pNode = sta.top(); sta.pop(); vec.push_back(pNode); pNode = pNode->right; } } int length = vec.size(); if(k <= length) { return vec[k - 1]; } return nullptr; }