一定要早日上岸鸭 · July 28, 2021 0

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

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

思路:DFS+哈希

第一次DFS来用哈希表存储节点和其父节点这样就可以在之后回溯得到距离为k的点

第二次DFS从target开始,以target为root,这样就可以用递归来找当前depth和k相同的节点了,需要注意的是,在回溯过程中会出现遍历过已经出现的数字的情况,因此我们需要记录下之前的节点是哪个。

ps:由于节点的值都不相同因此hashmap的key选择了值

代码:

// /** // * Definition for a binary tree node. // * public class TreeNode { // * int val; // * TreeNode left; // * TreeNode right; // * TreeNode(int x) { val = x; } // * } // */ class Solution { Map<Integer, TreeNode> hm = new HashMap<Integer, TreeNode>(); List<Integer> ret = new ArrayList<Integer>(); public void DFS_Hash(TreeNode root){ if(root==null) return; if(root.left!=null){ hm.put(root.left.val, root); DFS_Hash(root.left); } if(root.right!=null){ hm.put(root.right.val, root); DFS_Hash(root.right); } } public void DFS_Depth( TreeNode target, int cur_k, int k, int t){ if(target==null) return; // int temp = k; // TreeNode temp_target = target; // if(root.val==target.val){ // while(k>0){ // // 通过哈希表得到target的父节点: // TreeNode res = hm.get(temp_target.val); // temp_target = res; // k--; // } // ret.add(res.val); // k = temp; // } // System.out.println(target.val+" "+t); if(cur_k==k){ // System.out.println(target.val); ret.add(target.val); return; } if(target.left!=null && target.left.val!=t){ DFS_Depth(target.left, cur_k+1, k, target.val); } // System.out.println(target.right); if(target.right!=null && target.right.val!=t){ DFS_Depth(target.right, cur_k+1, k, target.val); } if(hm.get(target.val)!=null && hm.get(target.val).val !=t ){ // System.out.println(hm.get(target.val).val+" "+t); DFS_Depth(hm.get(target.val), cur_k+1, k, target.val); } } public List<Integer> distanceK(TreeNode root, TreeNode target, int k) { DFS_Hash(root); // System.out.println(hm.toString()); DFS_Depth(target, 0, k, target.val); return ret; } }

官方答案:

class Solution { Map<Integer, TreeNode> parents = new HashMap<Integer, TreeNode>(); List<Integer> ans = new ArrayList<Integer>(); public List<Integer> distanceK(TreeNode root, TreeNode target, int k) { // 从 root 出发 DFS,记录每个结点的父结点 findParents(root); // 从 target 出发 DFS,寻找所有深度为 k 的结点 findAns(target, null, 0, k); return ans; } public void findParents(TreeNode node) { if (node.left != null) { parents.put(node.left.val, node); findParents(node.left); } if (node.right != null) { parents.put(node.right.val, node); findParents(node.right); } } public void findAns(TreeNode node, TreeNode from, int depth, int k) { if (node == null) { return; } if (depth == k) { ans.add(node.val); return; } if (node.left != from) { findAns(node.left, node, depth + 1, k); } if (node.right != from) { findAns(node.right, node, depth + 1, k); } if (parents.get(node.val) != from) { findAns(parents.get(node.val), node, depth + 1, k); } } }