题目描述:
计算给定二叉树的所有左叶子之和。
示例:
3 / \ 9 20 / \ 15 7 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
思路:对树进行查找操作,最先想到的就是递归。假定所有的和是sum,则sum是针对一颗树而不是单个节点而言的。考察一个节点,如果它是NULL,那么num=0;否则考察它的孩子节点。对于左孩子而言,如果它是左叶子节点,那么sum=左叶子的val + 右孩子节点的sum。否则,sum= 左子树的sum+右子树的sum。写成代码如下:
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);
}
算法时间复杂度O(n),测试运行时间 4ms。
由于左孩子在在其父亲节点处就判断并计算完成,所以算法还可以稍作优化:但凡发现叶子节点,它一定不是左叶子。这样可以避免下一步对它两个为NULL的孩子节点的计算。代码如下:
int sumOfLeftLeaves(TreeNode* root) {
if(root==NULL) return 0;
if((root->left||root->right)==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);
}
时间复杂度仍旧是O(n),测试运行时间也是 4ms。
下面考虑把递归算法改成迭代。思路与非递归遍历算法是一样的,考察某个节点是否恰好是左叶子。
int sumOfLeftLeaves(TreeNode* root) {
if(root==NULL) return 0;
int ans=0;
stack<TreeNode*> s;
s.push(root);
while(s.size())
{
root=s.top();
s.pop();
if(root==NULL)
continue;
if((root->left || root->right)==NULL)
continue;
while(root->left)
{
s.push(root->right);
root=root->left;
}
//找到一个左叶子
if(root->right==NULL)
ans+=root->val;
else
s.push(root->right);
}
return ans;
}
时间复杂度 O(n),测试运行时间 4ms。
;