# LeetCode Easy 559. Maximum Depth of N-ary Tree

tags: leetcode

問題

• Explore
• Problems

アイデア

N-ary木の深さを測る問題です．

基本的に二分木と同じように解けます．(繰り返し文を使う必要があるかどうかくらいです)

解法1(recursive)

再帰関数を使ってDFSをして，深さを求めます．

• 根がないなら$0$
• そうでないなら深さを$0$で初期化します
• 深さを再帰的にmaxDepthを実行した値で更新します．
• 関数を実行するごとに深さが+1されるようにします(だから深さを$0$で初期化するのです)

計算量

ノードの数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • 木の深さに応じて平均で$O(\log N)$，最悪$O(N)$です

C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
  int maxDepth(Node* root) {
    if (!root)
      return 0;
    int depth(0);
    for (auto& child : root->children)
      depth = max(depth, maxDepth(child));
    return depth + 1;
  }
};

解法2(iterative)

Queueを使ってBFSをしてもStackを使ってDFSをしても解けます

ただ，書くのが面倒なので暇な時に...

# LeetCode Medium 429. N-ary Tree Level Order Traversal

tags: leetcode

Classicalの意味を一回辞書で調べてほしいと思う日々．

問題

• Explore
• Problems

アイデア

深さごとにノードの値をまとめて配列に入れ，それらの配列を1つの配列に格納します．

単にBFSをするという問題ですね．それにはQueueを使うのが便利です．

解法

• キューに現在の根を入れます
• そして，キューが空になるまで以下の処理を続けます
  • 現在キューに入っているノードの値を入れる配列を作ります
  • 現在のキューに入っているノードの値を全てその配列に入れます
  • その際にそのノードの子を全てキューに入れます
  • これが終わったらその配列を答えの配列に格納します

計算量

ノードが$N$だとする

• 時間計算量
  • $O(N)$
• 空間計算量
  • 毎回必要に成る配列は最悪$O(N)$
  • 答えに必要なものも同様に$O(N)$
  • よって，$O(N)$

C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
  vector<vector<int>> levelOrder(Node* root) {
    if (!root)
      return vector<vector<int>>();
    
    vector<vector<int>> res;
    queue<Node*> nodeQue;
    nodeQue.push(root);
    
    while (!nodeQue.empty()) {
      vector<int> curVals;
      int size = nodeQue.size();
      for (int i = 0; i < size; i++) {
        auto curNode = nodeQue.front();
        nodeQue.pop();
        curVals.push_back(curNode->val);
        for (auto& child : curNode->children)
          nodeQue.push(child);
      }
      res.push_back(curVals);
    }
    return res;
  }
};

# LeetCode Easy 590. N-ary Tree Postorder Traversal

tags: leetcode

問題

• Explore
• Problems

アイデア

おさらいをすると二分木の場合はPreorder, Inorder, Postorder traversalはそれぞれ根のノードがいつ探索されるかで分類されており，

• Preorder(根→左→右)
• Inorder(左→根→右)
• Postorder(左→右→根)

今回は2つより多くの子を持つ木に関してその探索を実装をします．

解法1(recursive)

Preorderは根から見て，子の見ていきました．

Postorderは子から見て，根を見ます．

計算量

ノードの数を$N$とする．

• 時間計算量
  • $O(N)$
• 空間計算量
  • 再帰の深さで必要なのは平均$O(\log N)$で最悪$O(N)$
  • 答えの配列に必要なのは$O(N)$
  • 全体だと$O(N)$だが，配列がない場合はiterativeに書くべし

C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
  vector<int> postorder(Node* root) {
    vector<int> res;
    addNodes(root, res);
    return res;
  }
private:
  void addNodes(Node* node, vector<int>& res) {
    if (!node)
      return;
    for (auto& child : node->children)
      addNodes(child, res);
    res.push_back(node->val);
  }
};

解法2(iterative)

暇になったら書きます

# LeetCode Easy 589. N-ary Tree Preorder Traversal

tags: leetcode

最近カップ中本にハマってしまいました．

問題

• Explore
• Problems

アイデア

おさらいをすると二分木の場合はPreorder, Inorder, Postorder traversalはそれぞれ根のノードがいつ探索されるかで分類されており，

• Preorder(根→左→右)
• Inorder(左→根→右)
• Postorder(左→右→根)

今回は2つより多くの子を持つ木に関してその探索を実装をします．

N-ary木にはPreorderとPostorderだけが定義されていて，やることは同じです．

解法1(recursive)

ノードから伸びるノードの配列に対して再帰的に関数を実行します．

それぞれ値を答えの配列に格納するだけです．

計算量

ノードの数を$N$とする．

• 時間計算量
  • $O(N)$
• 空間計算量
  • 再帰の深さで必要なのは平均$O(\log N)$で最悪$O(N)$
  • 答えの配列に必要なのは$O(N)$
  • 全体だと$O(N)$だが，配列がない場合はiterativeに書くべし

C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
  vector<int> preorder(Node* root) {
    vector<int> res;
    addNodes(root, res);
    return res;
  }
private:
  void addNodes(Node* node, vector<int>& res) {
    if (!node)
      return;
    
    res.push_back(node->val);
    for (auto& child : node->children)
      addNodes(child, res);
  }
};

解法2(iterative)

暇が出来たらやります()

Stackを使えば出来ます

# LeetCode Easy 112. Path Sum

tags: leetcode

問題

• Explore
• Problems

アイデア

与えられた木の根から葉までのたどる際に，与えられた値となるような経路はあるかという問題です．

解法

与えられた値にノードの値の合計がなるということは，与えられた値からノードの値を引いて$0$になるかどうかを調べれば良いです．

• 根がないときはfalseを返します
• 根があるときは与えられた関数を以下のように再帰的に実行します
  • 左右子がない
    • 現在のノードの値が合計と一致するかどうかを返します
  • 左右子がある
    • 現在のノードの値を合計から引き，左右子から再帰的に関数を実行する
  • 左子がある
    • 現在のノードの値を合計から引き，左子から再帰的に関数を実行する
  • 右子がある
    • 現在のノードの値を合計から引き，右子から再帰的に関数を実行する

計算量

ノードの数を$N$とします

• 時間計算量
  • $O(N)$
• 空間計算量
  • 再帰関数の深さは木の深さに依存します
  • 木の深さは平均で$O(\log N)$で最悪$O(N)$であり，それが空間計算量です

C++

/**
 * 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:
  bool hasPathSum(TreeNode* root, int sum) {
    if (!root)
      return false;
    int curVal = root->val;
    auto left = root->left, right = root->right;
    
    if (!left && !right)
      return (curVal == sum);
    else if (left && right)
      return hasPathSum(left, sum - curVal) || hasPathSum(right, sum - curVal);
    else if (left)
      return hasPathSum(left, sum - curVal);
    else // right
      return hasPathSum(right, sum - curVal);
  }
};