【DFS】993. 二叉树的堂兄弟节点 （简单）
让我们先看一下这道题目
我们可以从题目中得到这个重要信息：
0. 给定的两个节点必须处于同一深度才有可能返回true；
给定的两个节点的父节点不能是同一个，否则就是亲兄弟节点。
经过思考，不难发现这道题目最快的做法应该是BFS，但是由于本人对BFS理解不深刻，之后会补充BFS版本，先上一个DFS版本吧
我们设置两个map，一个用来存储当前节点的值和对应的深度，另一个用来存储当前节点的值和对应的父节点
private Map<Integer, Integer> depthMap = new HashMap<>();private Map<Integer,TreeNode> parentMap = new HashMap<>();
设置成成员变量，在进行dfs时，可以少传递参数。
在遍历二叉树的时候，用前序，中序，后序遍历都可以，在这里我们使用前序遍历
private void dfs(TreeNode node, TreeNode parent){if(node == null){return;}depthMap.put(node.val, parent == null ? 0 : depthMap.get(parent.val) + 1);parentMap.put(node.val, parent);dfs(node.left, node);dfs(node.right, node);}
所以这道题目的完整版本应该是这样
class Solution {//用双map来缓存数据private Map<Integer, Integer> depthMap = new HashMap<>();private Map<Integer,TreeNode> parentMap = new HashMap<>();public boolean isCousins(TreeNode root, int x, int y) {dfs(root, null);return depthMap.get(x) == depthMap.get(y) && parentMap.get(x) != parentMap.get(y);}private void dfs(TreeNode node, TreeNode parent){if(node == null){return;}depthMap.put(node.val, parent == null ? 0 : depthMap.get(parent.val) + 1);parentMap.put(node.val, parent);dfs(node.left, node);dfs(node.right, node);}}
今天的每日一题就到此结束了，BFS版本的答案之后我会补上，希望有不同思路的同学前来讨论研究～