404. 左叶子之和

递归

/**
 * 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 sumOfLeftLeaves(TreeNode root) {
        /**
        递归的遍历顺序为后序遍历（左右中），是因为要通过递归函数的返回值来累加求取左叶子数值之和。。
        递归三部曲：
        确定递归函数的参数和返回值
        判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int
        使用题目中给出的函数就可以了。
        确定终止条件
        依然是
        if (root == NULL) return 0;
        确定单层递归的逻辑
        当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。
         */
         if(root == null ) return 0;
         int leftValue = sumOfLeftLeaves(root.left);        //左
         int rightValue = sumOfLeftLeaves(root.right);      //右
                                                            // 中
         int midValue = 0;
         if(root.left != null && root.left.left == null && root.left.right == null ) {
             midValue = root.left.val;
         }
         int sum = midValue + leftValue + rightValue;
         return sum;
    }
}

迭代

/**
 * 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 sumOfLeftLeaves(TreeNode root) {
        //迭代
        //模拟先序遍历
        if(root == null ) return 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        int sum = 0;
        while(! stack.isEmpty() ) {
            TreeNode node = stack.pop();
            if(node.left != null && node.left.left == null && node.left.right == null ) {
                sum += node.left.val;
            }
            if(node.right != null ) stack.push(node.right);
            if(node.left != null ) stack.push(node.left);
        }
        return sum;
    }
}

层级遍历

/**
 * 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 sumOfLeftLeaves(TreeNode root) {
        //层级遍历
        if(root == null) return 0;
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        int sum =0;
        while(! que.isEmpty() ) {
            int size = que.size();
            while(size > 0) {
                TreeNode node = que.poll();
                if(node.left != null && node.left.left == null && node.left.right == null ) sum += node.left.val;
                if(node.left != null ) que.add(node.left);
                if(node.right != null) que.add(node.right);
                size --;
            }
        }
        return sum;
    }
}