java二叉树中所有距离为K的结点详解

KLQ 2020-07-14 09:14:21 java常见问答 8374

下面要给大家带来的是和java二叉树相关的内容,对于二叉树相信很多人都很熟悉了,那么下面再一起来详细的了解一下吧。

一个二叉树(具有根结点root),一个目标结点target,一个整数值K 。

返回到目标结点target距离为K的所有结点的值的列表。

答案能够以任何顺序返回。

示例一:

输入-root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2;

输出-[7,4,1];

分析-所要求的节点是和目标结点(值是5)距离是2的结点,值分别是7和4、1;

特别提醒-所输入的root以及target是树上的结点;以上的输入只是对这些对象进行了序列化描述。

序列化描述

提醒-给定的树为非空,并且,最多有K个结点;树上,每个结点都具有唯一的值 0 <= node.val <= 500;目标结点target为树上的结点;0 <= K <= 1000;

解法:

/**
 * 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:
        vector < int > distanceK(TreeNode * root, TreeNode * target, int K)
        {
            if (!root) return {};
            unordered_map < TreeNode * , vector < TreeNode * >> mp;
            queue < TreeNode * > qu;
            solution(root, nullptr, mp);
            qu.push(target);
            set < TreeNode * > s;
            s.insert(target);
            vector < int > res;
            while (!qu.empty())
            {
                if (K == 0)
                {
                    while (!qu.empty())
                    {
                        res.push_back(qu.front() - > val);
                        qu.pop();
                    }
                    return res;
                }
                int n = qu.size();
                while (n--)
                {
                    auto it = qu.front();
                    qu.pop();
                    for (auto c: mp[it])
                    {
                        if (s.find(c) != s.end())
                            continue;
                        qu.push(c);
                        s.insert(c);
                    }
                }
                K--;
            }
            return {};
        }
    void solution(TreeNode * root, TreeNode * pre, unordered_map < TreeNode * , vector < TreeNode * >> & mp)
    {
        if (root == nullptr) return;
        if (pre && root)
        {
            mp[pre].push_back(root);
            mp[root].push_back(pre);
        }
        solution(root - > left, root, mp);
        solution(root - > right, root, mp);
    }
};

你还想了解更多和java二叉树相关的内容吗?更多java经典实例以及java编程常见问题可以继续通过奇Q工具网来进行了解哦。

推荐阅读:

java二叉树遍历算法有哪些?如何操作?

java二叉树和为某一个值的路径如何实现?思路分享

java二叉树删除如何操作?