LintCode-900: Closest Binary Search Tree Value

내가 쓰는 방법은 이분귀속이다.루트->val > target에서 결과를 루트와 왼쪽 트리에서만 선택할 수 있습니다. 그렇지 않으면 루트와 오른쪽 트리에서만 선택할 수 있습니다.코드는 다음과 같습니다.

/**
 * 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 target: the given target
     * @return: the value in the BST that is closest to the target
    */
    int closestValue(TreeNode * root, double target) {
        if (!root) return INT_MAX;
        double currGap=abs(root->val-target);

        if (target>root->val) {
            if (root->right) {
                int rightCandidate = closestValue(root->right, target);
                double rightGap=abs(rightCandidate - target);
                if (rightGapreturn rightCandidate;
            }
            return root->val;

        } else {
            if (root->left) {
                int leftCandidate = closestValue(root->left, target);
                double leftGap=abs(leftCandidate - target);
                if (leftGapreturn leftCandidate;
            }
            return root->val;
        }
    }
};

또한 이 링크를 보면 간단명료하고 요약된 귀속과 교체 두 가지 해법을 제시하여 매우 좋다.http://rainykat.blogspot.com/2017/01/leetcode-270-closest-binary-search-tree.html반복 버전:

public class Solution {
    public int closestValue(TreeNode root, double target) {
        //         
        TreeNode kid = target < root.val ? root.left : root.right;
        //       ，        ，         
        if(kid == null) return root.val;
        //             
        int closest = closestValue(kid, target);
        //              ，       
        return Math.abs(root.val - target) < Math.abs(closest - target) ? root.val : closest;
    }
}

반복: We the node is in tree so traveling the BST and keep a value closet to target
Complexity: O(lgN)

public class Solution {
    public int closestValue(TreeNode root, double target) {
        int closest = root.val;
        while(root!=null){
            //if current root.val is closer, update closest 
            closest = Math.abs(closest-target)//do binary search
            root = targetreturn closest;
    }
}