力扣labuladong——一刷day47

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「遍历」的思维。

一、力扣993. 二叉树的堂兄弟节点

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int depthX = -1, depthY = -1;boolean flag = true;public boolean isCousins(TreeNode root, int x, int y) {fun(root,1,x,y);if(flag == false){return false;}if(depthX == depthY){return true;}return false;}public void fun(TreeNode root, int depth, int x, int y){if(root == null){return ;}if(root.val == x){depthX = depth;}if(root.val == y){depthY = depth;}if(root.left != null && root.right != null){if((root.left.val == x || root.left.val == y) && (root.right.val == x || root.right.val == y)){flag = false;}}fun(root.left,depth+1,x,y);fun(root.right,depth+1,x,y);}
}

二、力扣1315. 祖父节点值为偶数的节点和

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int sum = 0;public int sumEvenGrandparent(TreeNode root) {fun(root, null, null);return sum;}public void fun(TreeNode root, TreeNode parent, TreeNode grandParent){if(root == null){return;}if(grandParent != null && grandParent.val % 2 == 0){sum += root.val;}fun(root.left, root, parent);fun(root.right, root, parent);}
}

三、力扣1448. 统计二叉树中好节点的数目

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int count = 0;public int goodNodes(TreeNode root) {fun(root,Integer.MIN_VALUE);return count;}public void fun(TreeNode root, int preMax){if(root == null){return;}if(root.val >= preMax){preMax = root.val;count ++;}fun(root.left, preMax);fun(root.right, preMax);}
}

四、力扣1469. 寻找所有的独生节点

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Integer> res = new ArrayList<>();public List<Integer> getLonelyNodes(TreeNode root) {fun(root);return res;}public void fun(TreeNode root){if(root == null){return;}if(root.left == null && root.right != null){res.add(root.right.val);}if(root.left != null && root.right == null){res.add(root.left.val);}fun(root.left);fun(root.right);}
}