Java教程

算法_二叉树_左叶子之和

本文主要是介绍算法_二叉树_左叶子之和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 左叶子之和
    • 1.两种解法
      • 递归法
      • 迭代法
    • 2.总结
      • python
      • 算法

左叶子之和

leetcode链接

1.两种解法

递归法

思路:想找到所有的左叶子节点,就要先找到所有的叶子节点,然后把叶子节点中的左叶子节点再找出来,所以递归的一层操作就是:找到叶子节点if not root.left and not root.right: return -1,然后再看当前节点是否有左孩子并且判断左孩子是不是叶子节点,如果都满足则把这个叶子节点的值添加进num中,然后以同样的逻辑再遍历右孩子。

def sumOfLeftLeaves(root):

    num = []

    def traversal(root):

        # 判断是叶子节点
        if not root.left and not root.right:
            return -1

        # 如果有左孩子并且左孩子是叶子节点(即左叶子节点)
        if root.left and traversal(root.left)==-1:
            num.append(root.left.val)

        # 如果有右孩子
        if root.right:
            traversal(root.right)

    traversal(root)
    numsum = sum(num)

    return numsum

迭代法

迭代法就更直观了,把当前节点弹出,然后判断他的左孩子是不是左叶子节点,如果是就加上;然后把他的左孩子和右孩子入栈,以同样的逻辑循环即可。

def sumOfLeftLeaves(self, root: TreeNode) -> int:
        """
        Idea: Each time check current node's left node. 
              If current node don't have one, skip it. 
        """
        stack = []
        if root: 
            stack.append(root)
        res = 0
        
        while stack: 
            cur_node = stack.pop()
            # 判断是左叶子节点的逻辑
            if cur_node.left and not cur_node.left.left and not cur_node.left.right: 
                res += cur_node.left.val
                
            if cur_node.left: 
                stack.append(cur_node.left)
            if cur_node.right: 
                stack.append(cur_node.right)
                
        return res

2.总结

python

在函数中再定义函数时,定义数值变量时,存在局部变量还是全局变量的问题。但是如果使用容器来解,就都是全局变量,逻辑上比较清晰。(在递归法中有体现,所以我没定义一个numsum数值变量直接加,而是定义了一个num,然后在最后求和)

算法

灵活运用递归方法。

这篇关于算法_二叉树_左叶子之和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!