Skip to content

Latest commit

 

History

History
 
 

863.All-Nodes-Distance-K-in-Binary-Tree

863.All-Nodes-Distance-K-in-Binary-Tree

解法1:

本题的关键点是,任何两个节点AB之间的路径,都可以想象成有一个“拐点”O,其中OA是沿左子树向下的路径,OB是沿右子树向下的路径。我们可以递归处理每一个节点node,设想它是这个拐点,A是target并位于其中一个分支,那么如何在另一个分支中找到B?显然,假设我们能得到target到node->left之间的距离是t,那么我们只需要从node->right出发往下走k-2-t步,所抵达的节点就都是符合要求的B点。同理,如果target位于node->right分支,类似的处理。

需要单独处理的情况就是node==target,此时我们找的就是从node开始往下走k步到达的节点。

注意,DFS(node)函数的一个副产品就是可以返回target到达node的距离(假设target在node的下方),这样就可以避免再多写一个递归函数。

本题和543.Diameter-of-Binary-Tree的套路是一样的。也就是说,对于树里面任何两点之间的距离,优先去想它的拐点。

解法2:

将树的形式转化为图的形式。这样就可以target为起点进行BFS,寻找距离为k的点。

Leetcode Link