叶子节点之和问题

左叶子节点之和

题目描述

力扣链接🔗

代码分析

此题最重要的思路就是求左叶子节点，如果该节点的左叶子节点不为空，且左叶子节点的左右节点为空，那么该左节点就是叶子节点。

递归法

1. 确认函数返回值和参数
   判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int使用题目中给出的函数就可以了。
2. 确认中止条件
   在节点为空时，此时左右节点没有值，返回和为0。
3. 单层循环逻辑
   当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。

   /**
        * 递归法
        * @param root
        * @return
        */
        public int sumOfLeftLeaves(TreeNode root) {
            int sum = 0;
            if (root == null) {
                return 0;   // 递归停止的条件
            }
            int leftSum = 0, rightSum = 0;
            if (root.left != null) {
                rightSum = sumOfLeftLeaves(root.left); // 左孩子的所有左叶子节点之和
            }
            if (root.right != null) {
                leftSum = sumOfLeftLeaves(root.right); // 右孩子的所有左叶子节点之和
            }
            int midValue = 0;
            if (root.left != null && root.left.left == null && root.left.right == null) {
                midValue += root.left.val;  // 如果左节点的左右节点都为空，那么此左节点就是左叶子节点
            }
            sum = midValue + leftSum + rightSum;  // 左节点的左叶子节点之和加上右节点的做叶子节点之和即为此节点的做叶子节点之和
            return sum;
        }

迭代法

/**
 * 前序迭代法
 *
 * @param root
 * @return
 */
public int sumOfLeftLeaves(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    int sum = 0;
    if (root == null) {
        return sum;
    }
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.left != null && node.left.left == null && node.left.right == null) {
            sum += node.left.val;
        }
    }
    return sum;
}

层序遍历法

层次遍历，也是找到节点左孩子的左右节点为空的节点。

/**
 * 层序遍历
 *
 * @param root
 * @return
 */
public int sumOfLeftLeaves(TreeNode root) {
    int sum = 0;
    if (root == null) {
        return sum;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int len = queue.size();
        while (len-- > 0) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            if (node.left != null && node.left.left == null && node.left.right == null) sum += node.left.val;
        }
    }
    return sum;
}

前序遍历

/**
         * 迭代遍历
         *
         * @param root
         * @return
         */
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.val;
        }
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return sum;
}