【LeetCode】#404 Sum of Left Leaves

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

Example:

题目大意,给出一棵二叉树,求二叉树中左叶子节点的和。

(1)对二叉树进行递归遍历。判断当前节点的左孩子是否为空?(若不为空说明左孩子存在,这是第一步,下面接着判断…),并且当前节点的左孩子的左右孩子是否为空?(为空,说明上一步判断的节点为叶子节点,这是第二步,符合左叶子节点的条件)。

解法一

(2)上述的解法较容易理解,也可以将两个函数合成一个函数。

解法二

(3)非递归的解法。可以借助queue,将root节点push进去,pop取出节点并判断其左孩子节点是否为左叶子节点,处理完之后再将其左右孩子节点push进去,在处理queue中的节点…

解法三

类似的,也可以借助vector和stack容器来实现。可借鉴前面一题关于非递归使用queue和vector的解法二和解法三的思路:Invert Binary Tree

 

发表评论

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