LeetCode-二叉树中所有距离为 K 的结点

July 28, 2021

564 views

2528 words

# Problem - [二叉树中所有距离为 K 的结点](https://leetcode-cn.com/problems/all-nodes-distance-k-in-binary-tree/)

> **分析：**
>
> 根据题目可知我们需要寻找距离 `target`结点距离为 `k`的结点，若 `target`作为根节点我们便可以用深搜或者宽搜的方式找到。
>
> **算法：**
>
> 利用哈希表记录每个结点的父节点这样我们变可以以 `target`当作根节点取搜索距离其 `k`的结点。
>
> **代码思路：**
>
> 初始化一个哈希表 `mp`记录每个结点的父节点，构造函数 `findparent`来记录每个结点的父节点、函数 `findkdepth`搜索距离 `target`结点为 `k`的结点。

## 方法一：DFS

### 参考代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-4bb20a9bb64a8bd2867b5f80e1cf1ccd260' role="tab" data-target='#tabs-4bb20a9bb64a8bd2867b5f80e1cf1ccd260'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-7a21d637c0af299e079f4b92c52192a8651' role="tab" data-target='#tabs-7a21d637c0af299e079f4b92c52192a8651'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-4bb20a9bb64a8bd2867b5f80e1cf1ccd260' class="tab-pane fade active in">

```cpp
class Solution {
    vector<int> ans;
    unordered_map<int, TreeNode*> mp;
    void findparent(TreeNode* node) {
        if (node -> left) {
            mp[node -> left -> val] = node;
            findparent(node -> left);
        }
        if (node -> right) {
            mp[node -> right -> val] = node;
            findparent(node -> right);
        }
    }
    void findkdepth(TreeNode* node, TreeNode* parent, int depth, int k) {
        if (!node) return;
        if (depth == k) {
            ans.push_back(node -> val);
            return;
        }
        if (node -> left != parent) findkdepth(node -> left, node, depth + 1, k);
        if (node -> right != parent) findkdepth(node -> right, node, depth + 1, k);
        if (mp[node -> val] != parent) findkdepth(mp[node -> val], node, depth + 1, k);
    }
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        findparent(root);
        findkdepth(target, nullptr, 0, k);
        return ans;
    }
};
```

</div><div role="tabpanel" id='tabs-7a21d637c0af299e079f4b92c52192a8651' class="tab-pane fade  ">

```python
class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        ans, nodemp = list(), {root.val: None}

def findparent(node):
            if node.left:
                nodemp[node.left.val] = node
                findparent(node.left)
            if node.right:
                nodemp[node.right.val] = node
                findparent(node.right)
  
        def findkdepth(node, parent, depth, k):
            if not node: return
            if depth == k:
                ans.append(node.val)
                return
            if node.left != parent: findkdepth(node.left, node, depth + 1, k)
            if node.right != parent: findkdepth(node.right, node, depth + 1, k)
            if nodemp[node.val] != parent: findkdepth(nodemp[node.val], node, depth + 1, k)

findparent(root)
        findkdepth(target, None, 0, k)
  
        return ans;
```

</div>
</div>
</div>

~~ps：思路学习~~

### 复杂度分析：

* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$

Last modification：August 18, 2021