左叶子之和题目如下:
思路:求的是左叶子之和,不是最左侧叶子节点的和,所以即使是右子树,里面也会包含左叶子。使用递归的话,一定要明确递归三要素,这里递归的终止条件仍然是null时返回0(因为到空节点时,它的左叶子一定是0)。这里还需要明确的是如何判断是左叶子:通过它的父节点和它的左右孩子共同决定-如果它是父节点的左孩子,同时它的左右孩子都为空,那就说明他一定是左叶子。
单层递归的逻辑:当遇到左叶子节点的时候,记录数值,然后通过递归求取左子树左叶子之和,和 右子树左叶子之和,相加便是整个树的左叶子之和。
class Solution {public int sumOfLeftLeaves(TreeNode root) {//使用递归;注意左叶子不是左侧叶子,后序遍历if(root==null) return 0;int leftSumLeaves = sumOfLeftLeaves(root.left);//左int rightSumLeaves = sumOfLeftLeaves(root.right);//右//递归终止条件int midValue = 0;if(root.left != null && root.left.left == null && root.left.right == null){midValue = root.left.val;}int sum = leftSumLeaves + midValue + rightSumLeaves;//中return sum;}
}
找树左下角的值题目如下:
这道题用层序遍历的方法来做就会很简单,只需要在层序模版上判断一下是否到每层的第一个元素即可,代码如下:
class Solution {public int findBottomLeftValue(TreeNode root) {//层序遍历-只需要记录最后一层的第一个元素即可Deque<TreeNode> queue = new LinkedList<>();if(root == null) return 0;int result = 0;queue.offerLast(root);while(!queue.isEmpty()){int size = queue.size();for(int i = 0; i < size; i++){TreeNode node = queue.pollFirst();if(node.left != null) queue.offerLast(node.left);if(node.right != null) queue.offerLast(node.right);if(i==0) result = node.val;}}return result;}
}