270.最接近的二叉搜索树值

/*
 * @lc app=leetcode.cn id=270 lang=typescript
 *
 * [270] 最接近的二叉搜索树值
 */

// @lc code=start

//  Definition for a binary tree node.
class TreeNode {
	val: number;
	left: TreeNode | null;
	right: TreeNode | null;
	constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
		this.val = val === undefined ? 0 : val;
		this.left = left === undefined ? null : left;
		this.right = right === undefined ? null : right;
	}
}

interface DiffNode {
	diff: number;
	value: number;
}

function closestValue(root: TreeNode | null, target: number): number {
	/* 
        { 
          diff: xxx,  // 距离target距离
          value: xxx// 当前节点值
        }
    */
	// 存储所有有可能的节点
	let list: DiffNode[] = [];

	let current = root;
	while (current) {
		let obj: DiffNode = {
			diff: Math.abs(current.val - target),
			value: current.val,
		};
		list.push(obj);
		if (current.val > target) {
			current = current.left;
		} else if (current.val < target) {
			current = current.right;
		} else {
			current = null;
		}
	}

	// 处理存在相同距离的节点，返回最小值
	let sortList: DiffNode[] = list.sort((a, b) => a.diff - b.diff);
	sortList = sortList.filter(item=>item.diff == sortList[0].diff).sort((a, b) => a.value - b.value);
	
	return sortList[0].value;
}

const node1 = new TreeNode(1);
const node2 = new TreeNode(2);
const node3 = new TreeNode(3);
const node4 = new TreeNode(4);
const node5 = new TreeNode(5);

node4.left = node2;
node4.right = node5;
node2.left = node1;
node2.right = node3;

console.log(closestValue(node4, 3.5));
// @lc code=end

export default {};