一个网站的建设方案,网站开发接口,加速网页的加速器,网站开发人员的职业要求提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣513. 找树左下角的值二、力扣666. 路径总和 IV三、力扣1261. 在受污染的二叉树中查找元素四、力扣572. 另一棵树的子树 前言 二叉树的递归分为「遍历」… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣513. 找树左下角的值二、力扣666. 路径总和 IV三、力扣1261. 在受污染的二叉树中查找元素四、力扣572. 另一棵树的子树 前言 二叉树的递归分为「遍历」和「分解问题」两种思维模式这道题需要用到「遍历」的思维模式。
一、力扣513. 找树左下角的值
/*** 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 len -1;int res 0;public int findBottomLeftValue(TreeNode root) {fun(root,1);return res;}public void fun(TreeNode root, int depth){if(root null){return ;}if(depth len){len depth;res root.val;}fun(root.left, depth1);fun(root.right, depth1);}
}二、力扣666. 路径总和 IV
class Solution {int res 0,path 0;MapInteger,Integer map new HashMap();public int pathSum(int[] nums) {for(int a : nums){int value a%10;int pre a/10;map.put(pre,value);}fun(1,1);return res;}public int[] decode(int pre){return new int[]{pre/10,pre%10};}public int encode(int row, int index){return row * 10 index;}public void fun(int row, int index){int pre encode(row,index);if(!map.containsKey(pre)){return;}path map.get(pre);int left encode(row1,index*2-1);int right encode(row1,index*2);if(!map.containsKey(left) !map.containsKey(right)){res path;path - map.get(pre);return;}fun(row1,index*2-1);fun(row1,index*2);path - map.get(pre);}
}三、力扣1261. 在受污染的二叉树中查找元素
/*** 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 FindElements {MapInteger,Integer map new HashMap();TreeNode root null;public FindElements(TreeNode root) {fun(root,0);this.root root;}public boolean find(int target) {return map.containsKey(target);}public void fun(TreeNode root, int value){if(root null){return ;}map.put(value,1);root.val value;fun(root.left, value*21);fun(root.right, value*22);}
}/*** Your FindElements object will be instantiated and called as such:* FindElements obj new FindElements(root);* boolean param_1 obj.find(target);*/四、力扣572. 另一棵树的子树
/*** 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 {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root null){return subRoot null;}if(fun(root,subRoot)){return true;}return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);}public boolean fun(TreeNode root, TreeNode subRoot){if(root null subRoot null){return true;}if(root null || subRoot null){return false;}if(root.val ! subRoot.val){return false;}return fun(root.left,subRoot.left) fun(root.right,subRoot.right);}
}
