剑指offer54.二叉树的第K大节点

1.知识点：

二叉树的遍历方式如何写：

oid middleSearch(TreeNode* tr,stack<int> &stack){ if(tr) { middleSearch(tr -> left, stack); stack.push(tr -> val); middleSearch(tr -> right, stack); } }

就是一个中序遍历，左子树走到头，存一下，看看叶节点有没右子树，都没有返回父节点，看看有没有儿子。 然后就是二叉搜索树，左儿子都比老子小，右儿子都比老子大。 所以中序遍历的结果就是有序的一个数列，使用堆栈，pop n-1个就是答案

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void middleSearch(TreeNode* tr,stack<int> &stack){ if(tr) { middleSearch(tr -> left, stack); stack.push(tr -> val); middleSearch(tr -> right, stack); } } int kthLargest(TreeNode* root, int k) { stack<int> stack; middleSearch(root,stack); for(int i =0;i<k-1;i++){ stack.pop(); } return stack.top(); } };