LeetCode: 505.left叶子节点

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

示例：

3

/ \

9 20

/ \

15 7

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

解析

我们需要找到这样的节点

属于叶子节点

属于父节点的左子节点

方法一：用栈，dfs遍历，用全局变量res作为累积和。遍历的过程中传递该节点是否是左子节点。同时判断左右子节点是否为None，则可以知道是不是左叶子节点。

class Solution:

    def sumOfLeftLeaves(self, root: TreeNode) -> int:

        stack = []

        res = 0

        if not root:

            return res

        stack.append((root, 0))

        while len(stack) != 0:

            p, flag = stack.pop()

            if flag == 1:

                if p.left == p.right == None:

                    res += p.val

            if p.right:

                stack.append((p.right, 0))

            if p.left:

                stack.append((p.left, 1))    

        return res

方法二，用递归遍历。遍历到左叶子节点则加上左叶子节点的值。

class Solution:

    def sumOfLeftLeaves(self, root: TreeNode) -> int:

        self.res = 0

        def walk(p):

            if p:

                if p.left:

                    if p.left.left == p.left.right == None:

                        self.res += p.left.val

                    walk(p.left)

                if p.right:

                    walk(p.right)

        walk(root)

        return self.res

方法三， 仍是递归，没有使用全局变量。而是使用在递归函数内部累积的方式（即有返回值）。遍历到左叶子节点，则返回值就在此基础上加上右节点的遍历。

class Solution:

    def sumOfLeftLeaves(self, root: TreeNode) -> int:

        if root == None:

            return 0

        res = 0

        if root.left:

            if root.left.left == root.left.right == None:

               res += root.left.val

        return res + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

方法四，在递归的过程中，用一个形参记录该节点是否为左孩子点。和用stack遍历类似。

class Solution:

    def sumOfLeftLeaves(self, root: TreeNode) -> int:

        def cal(p, dir):

            if not p:

                return 0

            if p.left == p.right == None:

                if dir == 1:

                    return p.val

                else:

                    pass      

            return cal(p.left, 1) + cal(p.right, 0)

        return cal(root, 0)

方法五，当然还能用bfs遍历，遍历到左叶子节点就加上去。

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

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);

    }

};

class TreeNode {

    int val;

    TreeNode left;

    TreeNode right;

    TreeNode(int x) {

        val = x;

    }

}

class Solution {

    public int getLeafCount(TreeNode root) {

        if (root == null) {

            return 0;

        }

        if (root.left == null && root.right == null) {

            // 输出叶子节点

            System.out.println("leaf nodes:" + root.val);

            return 1;

        }

        return getLeafCount(root.left) + getLeafCount(root.right);

    }

}

public class Test {

    public static void main(String[] args) {

        Solution tree = new Solution();

        /* create a tree */

        TreeNode root = new TreeNode(3);

        root.left = new TreeNode(9);

        root.right = new TreeNode(20);

        function(){ //XM返佣 http://www.fx61.com/brokerlist/xm.html

        root.right.left = new TreeNode(15);

        root.right.right = new TreeNode(7);

        System.out.println(tree.getLeafCount(root));

    }

}