博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[LeetCode] Sum of Left Leaves 左子叶之和
阅读量:6815 次
发布时间:2019-06-26

本文共 2472 字,大约阅读时间需要 8 分钟。

 

Find the sum of all left leaves in a given binary tree.

Example:

3   / \  9  20    /  \   15   7There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

 

这道题让我们求一棵二叉树的所有左子叶的和,那么看到这道题我们知道这肯定是考二叉树的遍历问题,那么最简洁的写法肯定是用递归,由于我们只需要累加左子叶之和,那么我们在进入递归函数的时候需要知道当前结点是否是左子节点,如果是左子节点,而且该左子节点再没有子节点了说明其是左子叶,那么我们将其值加入结果res中,我们用一个bool型的变量,如果为true说明当前结点是左子节点,若为false则说明是右子节点,不做特殊处理,整个来说就是个递归的先序遍历的写法,参见代码如下:

 

解法一:

class Solution {public:    int sumOfLeftLeaves(TreeNode* root) {        if (!root || (!root->left && !root->right)) return 0;        int res = 0;        helper(root->left, true, res);        helper(root->right, false, res);        return res;    }    void helper(TreeNode* node, bool left, int& res) {        if (!node) return;        if (!node->left && !node->right && left) res += node->val;        helper(node->left, true, res);        helper(node->right, false, res);    }};

 

我们还可以写的更简洁一些,不需要写其他的函数,直接在原函数中检查当前节点的左子节点是否是左子叶,如果是的话,则返回左子叶的值加上对当前结点的右子节点调用递归的结果;如果不是的话,我们对左右子节点分别调用递归函数,返回二者之和,参见代码如下:

 

解法二:

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

 

我们也可以使用迭代来解,因为这道题的本质是遍历二叉树,所以我们可以用层序遍历的迭代写法,利用queue来辅助,注意对左子叶的判断和处理,参见代码如下:

 

解法三:

class Solution {public:    int sumOfLeftLeaves(TreeNode* root) {        if (!root || (!root->left && !root->right)) return 0;        int res = 0;        queue
q; q.push(root); while (!q.empty()) { TreeNode *t = q.front(); q.pop(); if (t->left && !t->left->left && !t->left->right) res += t->left->val; if (t->left) q.push(t->left); if (t->right) q.push(t->right); } return res; }};

 

我们也可以用stack来辅助,对比上面的解法,我们发现几乎一模一样,只是把queue换成了stack,但实际上遍历的顺序不同,这种方法是先序遍历的迭代写法,参见代码如下:

 

解法四:

class Solution {public:    int sumOfLeftLeaves(TreeNode* root) {        if (!root || (!root->left && !root->right)) return 0;        int res = 0;        stack
s; s.push(root); while (!s.empty()) { TreeNode *t = s.top(); s.pop(); if (t->left && !t->left->left && !t->left->right) res += t->left->val; if (t->left) s.push(t->left); if (t->right) s.push(t->right); } return res; }};

 

参考资料:

 

转载地址:http://fydzl.baihongyu.com/

你可能感兴趣的文章
腾讯抄你肿么办 ?
查看>>
java多线程的Fork/Join
查看>>
ftp 服务器的配置
查看>>
JavaScript的浏览器兼容性问题小结。
查看>>
Oracle Hint的用法
查看>>
Postfix邮件系统
查看>>
《编写可读代码的艺术》读书文摘--第一部分 表面层次的改进
查看>>
使用Nodejs创建基本的网站 Microblog--《Node.js开发指南》 3
查看>>
网管工作是否值得做下去?
查看>>
神行者PD10-adb push逃脱ro权限
查看>>
JPA(四)之实体关系一对一
查看>>
如何使用羊驼自动生成缩略图的功能。
查看>>
定制化Azure站点Java运行环境(1)
查看>>
inotify用法简介及结合rsync实现主机间的文件实时同步
查看>>
php 判断手机登陆
查看>>
git 问题
查看>>
Fedora18设置终端快捷键 和 桌面快捷方式
查看>>
取消NavigationBar左右两边的空隙
查看>>
Ubuntu 12.04 Gedit中文乱码解决办法
查看>>
修改symfony sfDoctrineGuardPlugin验证密码的方法
查看>>