南宁网站建公司电话号码,绍兴 网站建设,如何免费创建自己的小程序,小雨免费主机题目链接
力扣网404 左叶子之和 题目描述
给定二叉树的根节点 root #xff0c;返回所有左叶子之和。 示例 1#xff1a; 输入: root [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中#xff0c;有两个左叶子#xff0c;分别是 9 和 15#xff0c;所以返回 2…题目链接
力扣网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
思路分析
知识点递归、深度优先搜索
解析
这里是深度优先搜索的经典运用。题目要求找左叶子的和那么前提是它一定是一个叶子结点其次才判断它是否是左叶子。
这里采用一个bool函数再判断一下是否为叶子结点
如果根结点为空返回0
其次去往左子树找如果左子树存在且不为叶子结点的话继续往它的左子树找直到找到叶子结点为止如果是叶子结点直接返回它的值累加到一个变量里。
最后去往右子树找右子树的递归条件和左子树不一样因为右子树也会存在有左叶子结点的情况所以如果右子树是一个叶子结点的话就没必要递归了但如果不是的话就得往右子树里找。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/bool isleaves(struct TreeNode* root)
{return root-leftNULLroot-rightNULL;
}
int dfs(struct TreeNode* root)
{int ans0;if(root-left){ansisleaves(root-left)?root-left-val:dfs(root-left);}if(root-right!isleaves(root-right)){ansdfs(root-right);}return ans;}int sumOfLeftLeaves(struct TreeNode* root){return rootNULL?0:dfs(root);}
