提示：文章寫完后，目錄可以自動生成，如何生成可參考右邊的幫助文檔

---

前言

---

二叉樹的遞歸分為「遍歷」和「分解問題」兩種思維模式，這道題需要用到「遍歷」的思維模式。

一、力扣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, depth+1);fun(root.right, depth+1);}
}

二、力扣666. 路徑總和 IV

class Solution {int res = 0,path = 0;Map<Integer,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(row+1,index*2-1);int right = encode(row+1,index*2);if(!map.containsKey(left) && !map.containsKey(right)){res += path;path -= map.get(pre);return;}fun(row+1,index*2-1);fun(row+1,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 {Map<Integer,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*2+1);fun(root.right, value*2+2);}
}/*** 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);}
}