每日算法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;}
}