LeetCode: 863. All Nodes Distance K in Binary Tree

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;
    }
};
全部评论

相关推荐

屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
07-24 13:43
门头沟学院 Java
longerluck...:我猜说的是“你真**是个天才”
投递美团等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务