关注Java领域相关技术 记录有趣的事情

LeetCode-404. 左叶子之和

US-B.Ralph
US-B.Ralph
2020-09-19

问题地址

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;
    }
};
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

4 × 2 =