代码随想录算法训练营DAY18 | 二叉树 (5)

一、LeetCode 513 找树左下角的值

题目链接：513.找树左下角的值https://leetcode.cn/problems/find-bottom-left-tree-value/

思路一：递归+回溯+全局变量比深度。

class Solution {int Max_depth = 0;int result = 0;public int findBottomLeftValue(TreeNode root) {travel(root,0);return result;}public void travel(TreeNode root, int depth){if(root.left == null && root.right == null){if(depth > Max_depth){Max_depth = depth;result = root.val;}}if(root.left != null){depth++;travel(root.left,depth);//回溯depth--;}if(root.right != null){depth++;travel(root.right,depth);depth--;}return;}
}
/*** 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 int findBottomLeftValue(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int ans = 0;while(!queue.isEmpty()){int size = queue.size();for(int i = 0; i < size; i++){TreeNode node = queue.poll();//记录最后一行第一个值，即为树左下角的值if(i == 0){ans = node.val;}if(node.left != null){queue.offer(node.left);}if(node.right != null){queue.offer(node.right);}}}return ans;}
}

 二、LeetCode 112 路径总和

题目链接：112.路径总和https://leetcode.cn/problems/path-sum/

思路：前序遍历 + 叶子结点判断~

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {int sum = 0;return flag(root,targetSum,sum);}public boolean flag(TreeNode root, int target, int sum){if(root == null){return false;}//中 左 右sum += root.val;if(root.left == null && root.right == null){if(sum == target){return true;}}boolean left = flag(root.left, target, sum);boolean right = flag(root.right, target, sum);return left || right;}
}
/*** 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;*     }* }*/

 三、LeetCode 106 从中序与后序遍历序列构造二叉树

题目链接：106.从中序与后序遍历序列构造二叉树https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

思路：左闭右开，分割左右子树。

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);}public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd){//不满足左闭右开，返回空值if(inBegin >= inEnd || postBegin >= postEnd){return null;}//找到后序遍历最后一个元素在中序遍历中的位置int rootIndex = map.get(postorder[postEnd-1]);TreeNode root = new TreeNode(inorder[rootIndex]);int lenOfleft = rootIndex - inBegin;//利用中序遍历分左右子树，后序遍历左右子树节点个数与中序相同->分割后序遍历root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin+lenOfleft);root.right = findNode(inorder, rootIndex+1, inEnd, postorder, postBegin+lenOfleft, postEnd-1);return root;}
}
/*** 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;*     }* }*/

 四、小结

        昨天有点事情，今日补上~