LeetCode: 863. All Nodes Distance K in Binary Tree

题目描述

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
Output: [7,4,1]
Explanation: 
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.

Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.

Note:

The given tree is non-empty.
Each node in the tree has unique values 0 <= node.val <= 500.
The target node is a node in the tree.
0 <= K <= 1000.

解题思路 —— 递归求解

如 Example 1 所示，距离节点 5 的距离为 2 的节点可能出现在：
a. 距离为 2 的节点，在节点 5 的子树上（节点 7 和节点 4)：这种情况只需要算将节点 5 遍历其子树节点层数为 2的节点记录下来即可。

b. 距离为 2 的节点，在节点 5 的父亲节点，或兄弟子树上（节点 1）：这种情况需要找到最近公共祖先节点的距离和最近公共祖先节点到节点 5的距离和为 2 是节点，记录下来。如，节点 3 到节点 5 的距离加上节点 3 到节点到节点1的距离和为 2。

AC 代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
    // 找到目标节点在原树的位置
    // 返回 target 到 root 的距离
    int findTargetChild(TreeNode* root, TreeNode* target, int K, vector<int>& distanceKNode)
    {
        if(root == nullptr) return -1;
        else if(root == target)
        {
            findDistanceKFromChildren(root, K, distanceKNode);
            return 0;
        }
        else
        {
            int lt = findTargetChild(root->left, target, K, distanceKNode);
            int rt = findTargetChild(root->right, target, K, distanceKNode);

            if(lt != -1)
            {
                if(lt+1 == K)
                {
                    distanceKNode.push_back(root->val);
                }
                else
                {
                    findDistanceKFromChildren(root->right, K-lt-2, distanceKNode);
                }
                return lt+1;
            }
            else if(rt != -1)
            {
                if(rt+1 == K)
                {
                    distanceKNode.push_back(root->val);
                }
                else
                {
                    findDistanceKFromChildren(root->left, K-rt-2, distanceKNode);
                }
                return rt + 1;
            }
            else
            {
                return -1;
            }
        }
    }
    // 找到距离 root 为 K 的子节点
    void findDistanceKFromChildren(TreeNode* root, int K, vector<int>& distanceKNode)
    {
        if(root == nullptr) return;
        if(K == 0)
        {
            distanceKNode.push_back(root->val);
        }

        findDistanceKFromChildren(root->left, K-1, distanceKNode);
        findDistanceKFromChildren(root->right, K-1, distanceKNode);
    }
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        vector<int> distanceKNode;
        findTargetChild(root, target, K, distanceKNode);

        return distanceKNode;
    }
};