LeetCode-404. 左叶子之和

问题地址

LeetCode每日一题/2020-09-19

LeetCode404. 左叶子之和

问题描述

规则

• 计算给定二叉树的所有左叶子之和。

示例

• 示例1

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

解析

解题思路

• 左叶子的判定条件
  • 它是某个节点的左子节点；
  • 它是一个叶子结点；
• 因此我们遍历整棵树，当我们遍历到某个节点 \textit{node} 时，如果它的左子节点是一个叶子结点，那么就将它的左子节点的值累加计入答案。

数据操作分析

• 遍历整棵树，在遍历的过程中，判定某个节点是否满足左叶子的条件，判断条件：
  • 左子节点；
  • 叶子节点；

复杂度分析

编码实现

public class LeetCode0404_SumOfLeftLeaves {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int res = 0;
        if (root.left != null) {
            if (root.left.left != null || root.left.right != null) {
                res += sumOfLeftLeaves(root.left);
            } else {
                res += root.left.val;
            }
        }
        if (root.right != null) {
            res += sumOfLeftLeaves(root.right);
        }
        return res;
    }
}

官方解法

前言

一个节点为「左叶子」节点，当且仅当它是某个节点的左子节点，并且它是一个叶子结点。因此我们可以考虑对整棵树进行遍历，当我们遍历到节点 \textit{node} 时，如果它的左子节点是一个叶子结点，那么就将它的左子节点的值累加计入答案。
遍历整棵树的方法有深度优先搜索和广度优先搜索，下面分别给出了实现代码。

方法一：深度优先搜索

思路

复杂度分析

1. 时间复杂度：O(n)，其中 n 是树中的节点个数。
   2.空间复杂度：O(n)。空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下，树呈现链式结构，深度为 O(n)，对应的空间复杂度也为 O(n)。

编码实现

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return root != null ? dfs(root) : 0;
    }

    public int dfs(TreeNode node) {
        int ans = 0;
        if (node.left != null) {
            ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
        }
        if (node.right != null && !isLeafNode(node.right)) {
            ans += dfs(node.right);
        }
        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }
}

方法一：广度优先搜索

思路

复杂度分析

1. 时间复杂度：O(n)，其中 n 是树中的节点个数。
   2.空间复杂度：O(n)。空间复杂度与广度优先搜索使用的队列需要的容量相关，为 O(n)。

编码实现

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                if (isLeafNode(node.left)) {
                    ans += node.left.val;
                } else {
                    queue.offer(node.left);
                }
            }
            if (node.right != null) {
                if (!isLeafNode(node.right)) {
                    queue.offer(node.right);
                }
            }
        }
        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }
}

精彩评论

跳转地址1：404. 左叶子之和:【递归与非递归方法】详解

思路

• 首先要注意是判断左叶子呢，不是左子树，不要上来想着层序遍历。因为题目中其实没有说清楚左叶子究竟是什么节点，那么我来给出左叶子的明确定义：如果左节点不为空，且左节点没有左右孩子，那么这个节点就是左叶子
• 大家思考一下如下图中二叉树，左叶子之和究竟是多少？
  
• 其实是0，因为这棵树根本没有左叶子！ 所以左叶子节点之和为0那么判断左叶子，如果判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
• 判断的根据如下：

    if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
        sum = node->left->val;
    }

编码实现

递归写法代码如下：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        int sum = 0;
        if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
            sum = root->left->val;
        }
        return sum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
};

• 递归的过程其实就是二叉树的前序遍历，那么写过二叉树的同学都知道，既然是二叉树的前序遍历，能写出递归，就能写出非递归。如果对二叉树的各种递归和非递归的写法不熟悉，可以看我的这个题解：彻底吃透二叉树的前中后序递归法和迭代法！！
• 那么非递归版本善良登场，判断条件都是一样的

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        stack<TreeNode*> st;
        if (root == NULL) return 0;
        st.push(root);
        int result = 0;
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
                result += node->left->val;
            }
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return result;
    }
};