404. 左叶子之和

一、题目描述

计算给定二叉树的所有左叶子之和

示例：

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

二、思路

• 看到题目中的二叉树时，首先想到要用深度优先遍历或者广度优先遍历

• 接下来往下看左叶子之和，然后就想到了先序遍历、中序遍历、后序遍历。

• 题目中要求只计算左叶子之和，所以就考虑使用这三种遍历的非递归方式

  所以最后，还是选择使用的后序遍历的非递归实现

三、代码实现

1、先序遍历

后续补上

2、中序遍历

后续补上

3、后序遍历

# Definition for a binary tree node
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 首先判断root如果为None，返回值为0
        if not root:
            return 0

        else:
            # 保存左叶子节点的值
            result = []
            # 临时保存节点的栈
            stack = []
            stack.append(root)
            while stack:
                root = stack.pop()
                if root.left:
                    stack.append(root.left)
                    # 左子树节点为叶子结点
                    if not root.left.left and not root.left.right:
                        result.append(root.left.val)
                 if root.right:
                    stack.append(root.right)
             return sum(result)

四、结果

1、先序遍历

2、中序遍历

3、后序遍历

	运行时间		内存消耗
第一次	28ms	超过18%	12.7MB	超过93%
第二次	20ms	超过70%	12.8MB	超过80%

接下来，学习学习别人的思路，再接着优化吧。