1月10号代码随想录左叶子之和

2024-01-10 15:29:19

404.左叶子之和

给定二叉树的根节点?root?,返回所有左叶子之和。

示例 1:

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

示例?2:

输入: root = [1]
输出: 0

提示:

  • 节点数在?[1, 1000]?范围内
  • -1000 <= Node.val <= 1000

思路

不解释递归直接秒

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null){
            return 0;
        }
        if (root.left!=null&&root.left.left==null&&root.left.right==null){
           //这里需要注意一下也要递归右子树
            return root.left.val+sumOfLeftLeaves(root.right);
        }
        return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right);
    }
}

广搜解法就是普通的层序遍历,但我个人不喜欢广搜法,写起来比较麻烦。

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;
    }
}

总结

碰到二叉树类的题目,首先往深搜和广搜两个思路去想,遍历的时候也不要公式做题,多变变思路。

文章来源:https://blog.csdn.net/qq_39911747/article/details/135501155
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。