leetcode 404. 左叶子之和-递归算法与迭代算法

题目描述:

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

示例:

    3
   / \
  9  20
    /  \
   15   7

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

思路:对树进行查找操作,最先想到的就是递归。假定所有的和是sum,则sum是针对一颗树而不是单个节点而言的。考察一个节点,如果它是NULL,那么num=0;否则考察它的孩子节点。对于左孩子而言,如果它是左叶子节点,那么sum=左叶子的val + 右孩子节点的sum。否则,sum= 左子树的sum+右子树的sum。写成代码如下:

    int sumOfLeftLeaves(TreeNode* root) {
        //如果是空节点
        if(root==NULL) return 0;
        //如果它的左孩子恰好是左叶子
        if((root->left!=NULL) && (root->left->left==NULL)&&(root->left->right==NULL))
            return root->left->val+sumOfLeftLeaves(root->right);
        //左孩子不是左叶子的情况
        return sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
    }

算法时间复杂度O(n),测试运行时间 4ms。

由于左孩子在在其父亲节点处就判断并计算完成,所以算法还可以稍作优化:但凡发现叶子节点,它一定不是左叶子。这样可以避免下一步对它两个为NULL的孩子节点的计算。代码如下:

    int sumOfLeftLeaves(TreeNode* root) {
        if(root==NULL) return 0;
        if((root->left||root->right)==NULL) return 0;
        if((root->left!=NULL) && (root->left->left==NULL)&&(root->left->right==NULL))
            return root->left->val+sumOfLeftLeaves(root->right);
        return sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
    }

时间复杂度仍旧是O(n),测试运行时间也是 4ms。

下面考虑把递归算法改成迭代。思路与非递归遍历算法是一样的,考察某个节点是否恰好是左叶子。

int sumOfLeftLeaves(TreeNode* root) {
        if(root==NULL) return 0;
        int ans=0;
        stack<TreeNode*> s;
        s.push(root);
        while(s.size())
        {
            root=s.top();
            s.pop();
            if(root==NULL)
                continue;
            if((root->left || root->right)==NULL)
                continue;
            while(root->left)
            {
                s.push(root->right);
                root=root->left;
            }
            //找到一个左叶子
            if(root->right==NULL)
                ans+=root->val;
            else
                s.push(root->right);
        }
        return ans;
    }

时间复杂度 O(n),测试运行时间 4ms。

;