温馨提示×

LeetCode: 505.left叶子节点

发布时间:2020-07-10 04:35:36 来源:51CTO 阅读:232 作者:专注地一哥 栏目:编程语言

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

 

示例:

 

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

    }

}


免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

免费拨打  400 100 2938 免费拨打 400 100 2938
24小时售后技术支持 24小时售后技术支持
返回顶部 返回顶部