【4.10】回溯在二叉树中的应用

404. 左叶子之和 - 力扣（LeetCode）

首先将所有的节点都加入path中。不分左右。

在递归进右叶子节点后，只对右叶子节点进行操作即可。如果当前递归到的节点的右子节点为叶子节点，则要在path中排除该节点。总之，本题需要使用父节点来判断节点是不是不满足条件的右子节点，如果是，就将其弹出即可。

class Solution {List<Integer> path = new ArrayList<>();public int sumOfLeftLeaves(TreeNode root) {if(root == null || (root.left == null && root.right == null) ) return 0;traverse(root);int sum = 0;for(int i = 0 ; i< path.size() ; i ++){sum += path.get(i);}return sum;}void traverse(TreeNode root){if(root.left == null && root.right == null){path.add(root.val);}if(root.left != null){traverse(root.left);}if(root.right != null){traverse(root.right);if(root.right.left == null && root.right.right == null)path.remove(path.size() - 1);}}
}

513. 找树左下角的值 - 力扣（LeetCode）

解法一：简单的层序遍历

class Solution {Deque<TreeNode> q = new LinkedList<>();public int findBottomLeftValue(TreeNode root) {int ans = 0;if(root == null) return 0;q.offer(root);while(!q.isEmpty()){int size = q.size();for(int i = 0 ; i < size ; i ++){TreeNode cur = q.poll();if(i == 0){ans = cur.val;}if(cur.left != null){q.offer(cur.left);}if(cur.right != null){q.offer(cur.right);}}}return  ans;}
}

解法二：使用回溯算法，进入一个节点前，先增加该节点深度，退出一个节点后，减去该节点深度。

class Solution {int maxDepth = -1;int result = 0;int depth = 0;public int findBottomLeftValue(TreeNode root) {if(root == null) return result;if(root.left == null && root.right == null){if(depth > maxDepth){maxDepth = depth;result = root.val;}}if(root.left != null){depth ++;findBottomLeftValue(root.left);depth --;}if(root.right != null){depth ++;findBottomLeftValue(root.right);depth --;}return result;}
}

112. 路径总和 - 力扣（LeetCode）

回溯算法

class Solution {int target = 0;boolean flag = false;public boolean hasPathSum(TreeNode root, int targetSum) {if(root == null) return false;target = root.val;traverse(root , targetSum);return flag;}void traverse(TreeNode root , int targetSum){if(root == null) return;if(target == targetSum && root.left == null && root.right == null){flag = true;}if(root.left != null){target += root.left.val;traverse(root.left , targetSum);target -= root.left.val;}if(root.right != null){target += root.right.val;traverse(root.right , targetSum);target -= root.right.val;}}
}

654. 最大二叉树 - 力扣（LeetCode）

构造一个二叉树，就在递归中去构造。函数返回结果就是上一层递归中父节点的左右子节点。

class Solution {Map <Integer , Integer> map = new HashMap<>();public TreeNode constructMaximumBinaryTree(int[] nums) {for(int i = 0 ; i < nums.length ; i ++){map.put(nums[i], i);}return traverse(0 , nums.length - 1 , nums);}TreeNode traverse(int start , int end ,int [] nums){if(start > end){return null;}if(start == end){return new TreeNode(nums[start]);}int key = getMax(start , end , nums);TreeNode root = new TreeNode(key);int idx = map.get(key);root.left = traverse(start, idx - 1 ,nums);root.right = traverse(idx + 1,end, nums);return root;}int getMax(int start , int end,int [] nums){int max = 0;for(int i = start ; i <=end ; i ++){if(nums[i] > max){max = nums[i];}}return max;}
}

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

class Solution {Map <Integer,Integer> map = new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {for(int i = 0 ; i < inorder.length ; i ++){map.put(inorder[i] , i);}return findNode(inorder , 0 , inorder.length , postorder , 0 , postorder.length);}TreeNode findNode(int [] inorder , int inStart , int inEnd , int [] postorder , int pStart , int pEnd){if(inStart >= inEnd || pStart >= pEnd){return null;}//1. 先找到后序最后一个元素在中序中的位置。int idx = map.get(postorder[pEnd - 1]);//2. 根据位置找到中序的这个节点。TreeNode root = new TreeNode(inorder[idx]);//3. 保存中序遍历左子树的个数int leftSize = idx - inStart;/*4. root.left：对于中序遍历来说：inStart到idx都是左节点。对于后序遍历来说：pStart到pStart + leftSize 都是左节点。*/root.left = findNode(inorder , inStart ,idx, postorder ,pStart,pStart + leftSize);/*5. root.right对于中序遍历来说：idx + 1到inEnd都是右节点。对于后序遍历来说：pStart + leftSize到pEnd - 1都是右节点。*/root.right = findNode(inorder ,idx + 1, inEnd, postorder ,pStart + leftSize , pEnd - 1);return root;}
}