二叉树第k小元素求解：为何不能在Search方法中直接返回目标值？

你的代码实现 #

# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        if not root:
            return None
        out = []
        return self.Search(root,k,out)[k-1]
    def Search(self,root,k,out):
        if root:
        
            # iterate over the tree using DFS, and after the last iteration return the sorted list "out"
            self.Search(root.left,k,out)
            
            self.Search(root.right,k,out)
            out.append(root.val)
        return sorted(out)

你的疑问 #

为什么不能在Search方法中直接返回sorted(out)[k-1]？而必须将排序后的列表返回至kthSmallest方法后，再从中查找第k个元素？

解答 #

先搞明白你当前Search方法的递归执行逻辑：每一层递归都会返回排序后的out列表，但问题出在递归的执行顺序上。

举个实际例子：当程序遍历左子树时，左子树的递归调用会先执行，此时out里只收集了左子树的节点值。这时候如果在Search里直接返回sorted(out)[k-1]，返回的只是左子树里的第k小元素，根本没等右子树和根节点的值被加入out，结果肯定错误。

只有当最外层的Search调用（也就是从根节点开始的那次）执行完毕时，out才收集了所有节点的值，这时候排序后取第k-1位才是正确结果。但如果在递归过程中提前返回，每一层递归都会在自己的执行阶段就返回一个不完整的排序结果，完全不符合需求。

另外提个小优化：你现在用的是后序遍历（左→右→根），但二叉搜索树的中序遍历（左→根→右）本身就是升序的，根本不需要排序，收集到第k个元素直接返回就行，效率会高很多。不过回到你的核心问题：

你之所以不能在Search里直接返回，是因为递归的每一层都会触发return，但只有最后一次（根节点的Search执行完）的out才是完整的，提前返回会拿到不完整的结果。而你现在的写法里，虽然每一层递归都返回了sorted(out)，但只有最外层的返回值被kthSmallest拿到并使用，内层的返回值其实被忽略了，这才保证了结果正确。如果把return改成在Search里直接返回sorted(out)[k-1]，那第一次触发return的递归分支（比如左子树的最深处）就会直接返回一个错误的数值，整个递归直接终止，根本等不到所有节点被收集。

内容的提问来源于stack exchange，提问作者christheliz