每日算法Day11【左叶子之和、找树左下角的值、路径总和】
404.左叶子之和
算法链接:
404. 左叶子之和 - 力扣（LeetCode）
类型: 二叉树
难度: 简单
思路：要判断一个节点是否为左叶子节点，只能通过其父节点进行判断。
题解:
/*** 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;* }* }*/
//解法1：递归法
class Solution {public int sumOfLeftLeaves(TreeNode root) {if(root == null||root.left==null&&root.right==null){return 0;}int l = sumOfLeftLeaves(root.left);if(root.left!=null&&root.left.left==null&&root.left.right==null){l+= root.left.val;}int r = sumOfLeftLeaves(root.right);return l+r;}
}
//解法2：迭代法513.找树左下角的值
算法链接:
513. 找树左下角的值 - 力扣（LeetCode）
类型: 二叉树
难度: 中等
思路：层序遍历法，当每一层插入第一个（同一层最左边）的节点时，记录该节点并且将其返回。
递归法：前序遍历，判断当层数+1时记录当前值。（顺序：中、左、右）
题解:
/*** 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;* }* }*/
//解法1：层序遍历迭代法
class Solution {public int findBottomLeftValue(TreeNode root) {int res = 0;Deque<TreeNode> que = new LinkedList<>();que.offer(root);while(!que.isEmpty()){int size = que.size();for(int i = 0;i<size;i++){TreeNode poll = que.poll();if(i==0){res = poll.val;}if(poll.left!=null){que.offer(poll.left);}if(poll.right!=null){que.offer(poll.right);}}}return res;}
}
//解法2：递归法112. 路径总和
算法链接:
112. 路径总和 - 力扣（LeetCode）
类型: 二叉树
难度: 简单
题解:
/*** 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 hasPathSum(TreeNode root, int targetSum) {return search(root,0,targetSum);}boolean search(TreeNode root,int sum,int targetSum){if(root == null){return false;}sum+=root.val;if(root.left==null&&root.right==null){return sum==targetSum;}boolean l = search(root.left,sum,targetSum);boolean r = search(root.right,sum,targetSum);return l||r;}
}