関小君刷题记

题目大意：

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

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

示例 1：

输入：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" 实际上是树上的结点。
上面的输入仅仅是对这些对象进行了序列化描述。

提示：

1. 给定的树是非空的，且最多有 K 个结点。
2. 树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
3. 目标结点 target 是树上的结点。
4. 0 <= K <= 1000.

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=863

解题思路：

这道题是二叉树问题，看到树形结构，下意识要想到使用DFS搜索。关于dfs的相关知识之前的文章讲过很多次，这里就不再重复。对于本题，要求以目标节点为起点，找到与之相距为K的所有节点，这是典型的深度优先搜索，不过本题的难点在于，给出的模型是从上至下的单向关系图，我们需要将其转换为双向关系之后即可轻松解题。

public static class MyTreeNode {
    int val;
    MyTreeNode left;
    MyTreeNode right;
    MyTreeNode root;

    MyTreeNode(int x) {
        val = x;
    }
}

List<Integer> res;
MyTreeNode targetNode;
int targetVal;

public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
    res = new ArrayList<>();
    targetVal = target.val;
    if (K == 0) {
        res.add(target.val);
        return res;
    }
　　 // 构建关系图
    initMyTreeNode(root, null);
　　 // 有了关系图之后，从targetNode开始dfs就完了！
    dfs(targetNode, null, K - 1);
    return res;
}

private MyTreeNode initMyTreeNode(TreeNode target, MyTreeNode root) {
    if (target == null) {
        return null;
    }
    MyTreeNode myTreeNode = new MyTreeNode(target.val);
    myTreeNode.root = root;
    myTreeNode.left = initMyTreeNode(target.left, myTreeNode);
    myTreeNode.right = initMyTreeNode(target.right, myTreeNode);

    if (targetVal == target.val) {
        targetNode = myTreeNode;
    }

    return myTreeNode;
}
// 分别向root，left和right三个方向递归
private void dfs(MyTreeNode target, MyTreeNode preTarget, int K) {
    // preTarget的作用是避免走回头路
    if (target.left != null && (preTarget == null || target.left.val != preTarget.val)) {
        if (K == 0) {
            res.add(target.left.val);
        } else {
            dfs(target.left, target, K - 1);
        }
    }
    if (target.right != null && (preTarget == null || target.right.val != preTarget.val)) {
        if (K == 0) {
            res.add(target.right.val);
        } else {
            dfs(target.right, target, K - 1);
        }
    }
    if (target.root != null && (preTarget == null || target.root.val != preTarget.val)) {
        if (K == 0) {
            res.add(target.root.val);
        } else {
            dfs(target.root, target, K - 1);
        }
    }
}

本题解法执行时间为1ms。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-863-all-nodes-distance-k-in-binary-tree-解题思路分析/