题目描述

https://www.lintcode.com/problem/915/description
给出一棵二叉搜索树以及其中的一个节点，找到这个节点在这棵树中的中序前驱节点。

样例

输入: root = {2,1,3}, p = 1
输出: null

输入: root = {2,1}, p = 2
输出: 1

算法1

(dfs) $O(n)$

C++ 代码

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the given BST
     * @param p: the given node
     * @return: the in-order predecessor of the given node in the BST
     */

    TreeNode* pre = NULL;

    TreeNode * inorderPredecessor(TreeNode * root, TreeNode * p) {
        dfs(root, p);
        return pre;
    }

    void dfs(TreeNode* root, TreeNode* &p) {
        if (!root) return;
        dfs(root->left, p);
        if (root->val < p->val) pre = root;
        dfs(root->right, p);
    }
};

算法2

(迭代) $O(n)$

C++ 代码

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the given BST
     * @param p: the given node
     * @return: the in-order predecessor of the given node in the BST
     */



    TreeNode * inorderPredecessor(TreeNode * root, TreeNode * p) {
        TreeNode* pre = NULL;
        while (root != nullptr) {
            if (root->val >= p->val) {
                root = root->left;
            } else {
                pre = root;
                root = root->right;
            }
        }
        return pre;
    }

};