剑指offer--二叉树

智子lock / 2023-07-26 / 原文

第3题：二叉搜索树的第k个节点

描述
给定一棵结点数为n的二叉搜索树，请找出其中的第k小的TreeNode结点值。

返回第k小的节点值即可
不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
保证n个节点的值不一样

思路

递归中序遍历
二叉搜索树：左子树的元素都小于根节点，右子树的元素都大于根节点。因此它的中序遍历（左中右）序列正好是由小到大的次序。
- 具体做法
  1. 设置全局变量count记录遍历了多少个节点，res记录第k个节点。
  2. 另写一函数进行递归中序遍历，当节点为空或者超过k时，结束递归，返回。
  3. 优先访问左子树，再访问根节点，访问时统计数字，等于k则找到。
  4. 最后访问右子树

class Solution {
public:
	//记录返回的节点
	TreeNode* res = NULL;
	//记录中序遍历了多少个
	int count = 0;
	//当遍历到节点为空或者超过k时，返回
	void midOrder(TreeNode* root, int k){
		if(root == NULL || count > k) 
			return;
		midOrder(root->left, k);
		count++;
		//只记录第k个
		if(count == k)
			res = root;
		midOrder(root->right, k);
	}
	int KthNode(TreeNode* proot, int k) {
		midOrder(proot, k);
		if(res)
			return res->val;
		//二叉树为空，或是找不到
		else 
			return -1;
	}
};

栈

具体做法
1. 用栈记录当前节点，不断往左深入，直到左边子树为空。
2. 再弹出栈顶（即为当前子树的父节点），访问该节点，同时计数
3. 然后再访问其右子树，其中没棵子树都遵循左中右的次序
4. 直到第k个节点返回，如果遍历结束也没找到，则返回-1.
代码

class Solution{
	public:
		int kthNode(TreeNode* proot,int k){
			if(proot==nullptr) return -1;
			int count = 0;
			TreeNode* p = nullptr;
			stack<TreeNode*> s;
			while(!s.empty()||proot!=nullptr){
				while(proot!=nullptr){
					s.push(proot);
					proot = proot->left;
				}
				p = s.top();
				s.pop();
				count++;
				if(count==k) return p->val;
				proot = p->right;
			}
			return -1;
		}
}