题目描述

找二叉排序树中，结点值小于 x 且是所有小于 x 的结点中最大的结点。 其中，二叉排序树定义如下：

typedef struct BTNode { int val; struct BTNode *lchild; struct BTNode *rchild; } BSTNode, *BiTree;

例如找上图<35所构成列表中的最大值：34

---

算法思路

用max记录当前遍历到的比x小的最大值，使用bt遍历二叉排序树；在 bt->val >= x 的结点的左子树中查找；在 bt->val < x 的结点的右子树中查找；直到该结点为叶子结点。 int FindMax(BiTree bt, int x) { int max = INT_MIN; while(bt != NULL) { if(bt->val >= x) bt = bt->lchild; else { max = bt->val; bt = bt->rchild; } } return max; }

时空复杂度 $O(n)$