993.二叉树的堂兄弟节点

题目描述：

image.png

解：

因为需要知道父节点和深度，所以需要用dfs或bfs的方式去遍历，选择dfs的原因是比bfs更好写…

  1. class Solution {
  2.     int x; //记录x
  3.     int xDepth;
  4.     TreeNode xParent;
  5.     boolean xFound = false;
  7.     int y; //记录y
  8.     int yDepth;
  9.     TreeNode yParent;
  10.     boolean yFound = false;
  12.     private void dfs(TreeNode root,int depth,TreeNode parent) {
  13.         if(root == null) {
  14.             return;
  15.         }
  16.         if(xFound && yFound) { //都找到了就可以返回了
  17.             return;
  18.         }
  19.         if(root.val == x) {
  20.             xDepth = depth;
  21.             xParent = parent;
  22.             xFound = true;
  23.         } else if(root.val == y) {
  24.             yDepth = depth;
  25.             yParent = parent;
  26.             yFound = true;
  27.         }
  28.         if(xFound && yFound) {
  29.             return;
  30.         }
  31.         dfs(root.left,depth+1,root);
  32.         dfs(root.right, depth + 1, root);
  33.     }
  35.     public boolean isCousins(TreeNode root, int x, int y) {
  36.         this.x = x;
  37.         this.y = y;
  38.         dfs(root,0,null);
  39.         return xDepth == yDepth && xParent != yParent;
  40.     }
  41. }