golang 解法, 执行用时: 0 ms, 内存消耗: 5.4 MB, 提交时间: 2023-10-21 22:47:14

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "math"

// 中序遍历的同时进行收集k个元素的任务
// 显然k个元素一定是连续的，那么我们可以维护一个长度为k的滑动窗口，当窗口中的元素少于k时，扩展窗口。元素数量已经等于k时，
//如果下一个元素比窗口最左端的元素更靠近target，窗口右移一位，否则说明已经找到了最靠近的k个元素
func closestKValues(root *TreeNode, target float64, k int) []int {
	var ans []int
	var stack []*TreeNode
	for len(stack) > 0 || root != nil {
		if root != nil {
			stack = append(stack, root)
			root = root.Left
		} else {
			root = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if len(ans) < k {
				ans = append(ans, root.Val)
			} else if math.Abs(float64(root.Val)-target) < math.Abs(float64(ans[0])-target) {
				ans = ans[1:]
				ans = append(ans, root.Val)
			} else {
				break
			}
			root = root.Right
		}
	}
	return ans
}

golang 解法, 执行用时: 8 ms, 内存消耗: 5.4 MB, 提交时间: 2023-10-21 22:45:37

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
import "math"

func closestKValues(root *TreeNode, target float64, k int) []int {
	out := []int{}
	st := []*TreeNode{}
	n := root
	for nil != n || 0 != len(st) {
		for nil != n {
			st = append(st, n)
			n = n.Left
		}
		n = st[len(st)-1]
		st = st[:len(st)-1]
		if len(out) < k {
			out = append(out, n.Val)
		} else if math.Abs(float64(n.Val)-target) < math.Abs(float64(out[0])-target) {
			out = append(out, n.Val)
			out = out[1:]
		} else {
			break
		}
		n = n.Right
	}
	return out
}

cpp 解法, 执行用时: 12 ms, 内存消耗: 21.4 MB, 提交时间: 2023-10-21 22:45:21

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        stack<TreeNode*> less;
        stack<TreeNode*> more;

        while(root) {
            if (root->val <= target) {
                less.push(root);
                root = root->right;
            } else {
                more.push(root);
                root = root->left;
            }
        }

        vector<int> ans;
        while(k) {
            k--;
            float l = less.empty() ? INT_MAX : abs(less.top()->val - target);
            float r = more.empty() ? INT_MAX : abs(more.top()->val - target);

            if (l < r) {
                TreeNode* p = less.top();
                less.pop();
                ans.push_back(p->val);
                p = p->left;
                while(p!=NULL) {
                    less.push(p);
                    p = p->right;
                }
            } else {
                TreeNode* p = more.top();
                more.pop();
                ans.push_back(p->val);
                p = p->right;
                while(p!=NULL) {
                    more.push(p);
                    p = p->left;
                }

            }
        }

        return ans;
    }
};

python3 解法, 执行用时: 52 ms, 内存消耗: 18.7 MB, 提交时间: 2023-10-21 22:45:05

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestKValues_3(self, root: TreeNode, target: float, k: int) -> List[int]:
            # 解法3:非递归方法
            if not root:
                return
            DONE = 1 # 已读结点
            UNDO = 0 # 未读结点
            res = []
            stack = [(root, UNDO)]
            while stack:
                node, status = stack.pop()
                if not node:
                    continue
                if status == UNDO:
                    stack.append((node.right, UNDO))
                    stack.append((node, DONE))
                    stack.append((node.left, UNDO))
                elif status == DONE:
                    if k > len(res):
                        res.append(node.val)
                    elif abs(res[0] - target) > abs(node.val - target):
                        res.pop(0)
                        res.append(node.val)
            return res
        
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        if not root: retrun 
            # 解法2:中序遍历（左-根-右），遍历过程中判断是否已经在res并且比较第0个值与target
        res = []
        self.inorder(root, target, k, res)
        return res
            
    def inorder(self, root, target, k, res):
        if not root: return
        self.inorder(root.left, target, k, res)
        if k > len(res):
            res.append(root.val)
        elif abs(res[0] - target) > abs(root.val - target):
            res.pop(0)
            res.append(root.val)
        else: return
        self.inorder(root.right, target, k, res)

python3 解法, 执行用时: 52 ms, 内存消耗: 18.8 MB, 提交时间: 2023-10-21 22:41:04

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        ans = []
        arr = []
        def dfs(root):# 中序遍历
            if root is None:
                return
            dfs(root.left)
            arr.append(root.val)
            dfs(root.right)
        dfs(root)
        right = bisect_left(arr, target)
        left = right - 1
        for i in range(k):# 双指针
            if left>=0 and right < len(arr):
                if abs(arr[left] - target) <= abs(arr[right] - target):
                    ans.append(arr[left])
                    left -= 1
                else:
                    ans.append(arr[right])
                    right += 1
            elif left>=0:
                ans.append(arr[left])
                left -= 1
            else:
                ans.append(arr[right])
                right += 1
        return ans

java 解法, 执行用时: 0 ms, 内存消耗: 43.4 MB, 提交时间: 2023-10-21 22:40:42

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Queue<Integer> q = new LinkedList();
        inorder(q, root, target, k);
        return new ArrayList(q);
    }
    private void inorder(Queue<Integer> q, TreeNode root, double target, int k) {
        if (root == null) return;
        inorder(q, root.left, target, k);
        if (q.size() == k) {
            if (Double.compare(Math.abs(q.peek() - target), Math.abs(root.val - target)) > 0) {
                q.poll();
                q.offer(root.val);
            } else return;
        } else {
            q.offer(root.val);
        }
        inorder(q, root.right, target, k);
    }
}

java 解法, 执行用时: 2 ms, 内存消耗: 43.6 MB, 提交时间: 2023-10-21 22:40:22

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Stack<TreeNode> smaller = new Stack();
        Stack<TreeNode> larger = new Stack();

        while (root != null) {
            if (root.val <= target) {
                smaller.push(root);
                root = root.right;
            } else {
                larger.push(root);
                root = root.left;
            }
        }

        List<Integer> ans = new ArrayList();
        for (; k > 0; k--) {
            double leftDif = smaller.isEmpty() ? Double.MAX_VALUE : target - smaller.peek().val;
            double rightDif = larger.isEmpty() ? Double.MAX_VALUE : larger.peek().val - target;

            if (leftDif <= rightDif) {
                TreeNode node = smaller.pop();
                ans.add(node.val);
                node = node.left;
                while (node != null) {
                    smaller.push(node);
                    node = node.right;
                }
            } else {
                TreeNode node = larger.pop();
                ans.add(node.val);
                node = node.right;
                while (node != null) {
                    larger.push(node);
                    node = node.left;
                }
            }
        }

        return ans;
    }
}

java 解法, 执行用时: 3 ms, 内存消耗: 43.5 MB, 提交时间: 2023-10-21 22:39:57

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> closestKValues = new ArrayList<Integer>();
        int size = 0;
        List<Integer> inorderTraversal = inorderTraversal(root);
        int length = inorderTraversal.size();
        int index = binarySearch(inorderTraversal, target);
        int index1 = -1, index2 = -1;
        if (index >= 0) {
            closestKValues.add(inorderTraversal.get(index));
            size++;
            index1 = index - 1;
            index2 = index + 1;
        } else {
            index = -index - 1;
            index1 = index - 1;
            index2 = index;
        }
        while (size < k && index1 >= 0 && index2 < length) {
            int num1 = inorderTraversal.get(index1), num2 = inorderTraversal.get(index2);
            if (target - num1 <= num2 - target) {
                closestKValues.add(num1);
                index1--;
            } else {
                closestKValues.add(num2);
                index2++;
            }
            size++;
        }
        while (size < k && index1 >= 0) {
            int num1 = inorderTraversal.get(index1);
            closestKValues.add(num1);
            index1--;
            size++;
        }
        while (size < k && index2 < length) {
            int num2 = inorderTraversal.get(index2);
            closestKValues.add(num2);
            index2++;
            size++;
        }
        return closestKValues;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> inorderTraversal = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            TreeNode visitNode = stack.pop();
            inorderTraversal.add(visitNode.val);
            node = visitNode.right;
        }
        return inorderTraversal;
    }

    public int binarySearch(List<Integer> list, double target) {
        int low = 0, high = list.size() - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = list.get(mid);
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -low - 1;
    }
}