左葉の合計Leetcodeソリューション


難易度 簡単に
よく聞かれる Adobe
ツリートラバーサル

この問題では、すべての左の葉の合計をバイナリで見つける必要があります ツリー。 「」と呼ばれる葉左葉」は、ツリー内の任意のノードの左の子である場合。

左葉の合計Leetcodeソリューション

  

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

アプローチ

再帰を使用して二分木を走査できます。 いずれかのノードに左の子があり、それもリーフである場合、左の子の値を合計に追加できます。 ただし、このアプローチでは再帰的なスタックスペースを使用します。

メモリスペースを節約できる他のトラバーサルを使用できますか?

モリスインオーダートラバーサル すべてのノードを繰り返し訪問するように実装できます。 左葉の子があるかどうかを確認し、それに応じて結果に値を追加します。 これが最適なアプローチです。 問題によってツリーの構造を変更できる場合にのみ、「MorrisInorderトラバーサル」を実装できることに注意してください。

アルゴリズム(再帰的)

  1. 関数を作成する sumOfLeftLeaves() 渡された葉の左葉の合計を返します ルート
  2. 木の根が NULL
    • ゼロを返す
  3. 現在のルートに左の子があり、それが 葉っぱ
    • その値を返す+ sumOfLeftLEaves(root-> left)+ sumOfLeftLeaves(root-> right)
  4. sumOfLeftLEaves(root-> left)+ sumOfLeftLeaves(root-> right)を返します

アルゴリズム(Morris Inorder)

  1. Morris Inorder Traversalを使用してバイナリをトラバースします。
    • 任意のノードの左側のサブツリーの前の順序をそれ自体にスレッド化します。
    • スレッドがすでに存在する場合は、スレッドを解除して、ツリーの元の構造を保持します。
  2. いずれかのノードの左の子が葉である場合は、それを結果に追加します。
  3. 結果を印刷します。

製品の導入

左葉の合計のC ++プログラムLeetcodeソリューション

再帰的アプローチ

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int sumOfLeftLeaves(treeNode* root)
{
    if(root)
    {
        if(root->left && !root->left->left && !root->left->right)
            return root->left->value + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
        return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
    return 0;
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(4);
    root->right = new treeNode(7);
    root->right->left = new treeNode(9);
    root->right->right =  new treeNode(4);

    cout << "Sum is " << sumOfLeftLeaves(root) << "\n";


    return 0;
}

最適な方法

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int sumOfLeftLeaves(treeNode* root)
{
    int sum = 0;
    while(root != NULL)
    {
        if(root->left == NULL)
        {
            if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
                sum += root->left->value;
            root = root->right;
        }
        else
        {
            treeNode* temp = root->left;
            while(temp->right != NULL && temp->right != root)
                temp = temp->right;

            if(temp->right == NULL)
            {
                temp->right = root;
                root = root->left;
            }
            else
            {
                temp->right = NULL;
                if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
                    sum += root->left->value;
                root = root->right;
            }
        }
    }
    return sum;
}



int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(4);
    root->right = new treeNode(7);
    root->right->left = new treeNode(9);
    root->right->right =  new treeNode(4);

    cout << "Sum is " << sumOfLeftLeaves(root) << "\n";


    return 0;
}
Sum is 13

左葉の合計のJavaプログラムLeetcodeソリューション

再帰的アプローチ

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class sum_of_left_leaves
{
    public static int sumOfLeftLeaves(treeNode root)
    {
        if(root == null)
            return 0;
        if(root.left != null && root.left.left == null && root.left.right == null)
            return root.left.value + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(4);
        root.right = new treeNode(7);
        root.right.left = new treeNode(9);
        root.right.right =  new treeNode(4);

        System.out.println("Sum is " + sumOfLeftLeaves(root));
    }
}

最適な方法

int sum = 0;
        while(root != null)
        {
            if(root.left == null)
            {
                if(root.left != null && root.left.left == null && root.left.right == null)
                    sum += root.left.value;
                root = root.right;
            }
            else
            {
                treeNode temp = root.left;
                while(temp.right != null && temp.right != root)
                    temp = temp.right;

                if(temp.right == null)
                {
                    temp.right = root;
                    root = root.left;
                }
                else
                {
                    temp.right = null;
                    if(root.left != null && root.left.left == null && root.left.right == null)
                        sum += root.left.value;
                    root = root.right;
                }
            }
        }
        return sum;
Sum is 13

左葉の合計の複雑さの分析Leetcodeソリューション

時間の複雑さ

オン)、 再帰的アプローチと反復的アプローチの両方でツリー全体をXNUMX回トラバースします。

スペースの複雑さ

O(1) Morris InorderTraversalを使用します。 再帰的アプローチは オン) メモリ内のスペース.