Leetcode Binary Tree 用の関数一覧

#include "leetcode.h"
#include "mydefine.h"
/*
void dfs(TreeNode* n) {
    //End
    if (n == nullptr) return;
    //Process
    //Transition
    dfs(n->left);
    dfs(n->right);
}
*/
/*
void dfs(TreeNode* n) {
    if (n == nullptr) return;
    dfs(n->left);
    dfs(n->right);
}
*/
/*
    bool isLeaf(TreeNode* n) { return n != nullptr && n->left == nullptr && n->right == nullptr; }
*/
class BinaryTree_Solution {
public:
    bool isLeaf(TreeNode* n) { return n != nullptr && n->left == nullptr && n->right == nullptr; }

    //+-------------------------+
    //| List up all Leaf depth; |
    //+-------------------------+
    set<int> v_depth;
    void leaf_depth(TreeNode* n, int d = 1) {
        if (n == nullptr) return;
        if (isLeaf(n))  v_depth.insert(d);
        leaf_depth(n->left, d + 1);
        leaf_depth(n->right, d + 1);
    }

    //max depth up Leaf depth Node which has children
    int tmp = 0;
    int maxD = 0;
    int maxDepth(Node* n) {
        if (n == nullptr) return tmp;

        tmp++;
        maxD = max(tmp, maxD);
        rep(i, 0, n->children.size()) {
            maxDepth(n->children[i]);
        }
        tmp--;
        return maxD;
    }

    //Calculate height at one node.
    int node_height(TreeNode* n, int d = 1) {
        if (n == nullptr) return 0;
        if (isLeaf(n)) return d;
        return max(node_height(n->left, d + 1), node_height(n->right, d + 1));
    }

    //+---------------------------------+
    //| List up nodes from root to leaf |
    //+---------------------------------+
    VVi root_leaves;
    Vi root_leaf;
    void listup_root_leaf(TreeNode* n) {
        if (n == nullptr) return;
        root_leaf.push_back(n->val);
        if (isLeaf(n)) {
            root_leaves.push_back(root_leaf);
            return;
        }
        if (n->left != nullptr) {
            listup_root_leaf(n->left);
            root_leaf.pop_back();
        }
        if (n->right != nullptr) {
            listup_root_leaf(n->right);
            root_leaf.pop_back();
        }
    }

    //+-------------------------------------------+
    //| List up same height nodes; <height,nodes> |
    //+-------------------------------------------+
    //vector<TreeNode*>
    map<int, vector<TreeNode*>> m_nodes;
    void listUpSameLevelNodes(TreeNode* n, int d = 1) {
        if (n == nullptr) return;
        m_nodes[d].push_back(n);
        listUpSameLevelNodes(n->left, d + 1);
        listUpSameLevelNodes(n->right, d + 1);
    }
    //vector<int>
    map<int, vector<int>> m_nodes_val;
    void listUpSameLevelNodes_val(TreeNode* n, int d = 1) {
        if (n == nullptr) return;
        m_nodes_val[d].push_back(n->val);
        listUpSameLevelNodes_val(n->left, d + 1);
        listUpSameLevelNodes_val(n->right, d + 1);
    }
    //set<int>
    map<int, set<int>> m_nodes_s;
    void listUpSameLevelNodes_p(TreeNode* n, int d = 1) {
        if (n == nullptr) return;
        m_nodes_s[d].insert(n->val);
        listUpSameLevelNodes(n->left, d + 1);
        listUpSameLevelNodes(n->right, d + 1);
    }

    //+---------------------+
    //| List up all leaves; |
    //+---------------------+
    vector<TreeNode*> v_leaves;
    void listUpLeaves(TreeNode* n) {
        if (n == nullptr) return;
        if (isLeaf(n)) {
            v_leaves.push_back(n);
            return;
        }
        listUpLeaves(n->left);
        listUpLeaves(n->right);
    }
    void listUpLeaves_val(TreeNode* n, vector<int>& v) {
        if (n == nullptr) return;
        if (isLeaf(n)) {
            v.push_back(n->val);
            return;
        }
        listUpLeaves_val(n->left, v);
        listUpLeaves_val(n->right, v);
    }

    //+---------------------+-------------+
    //| Sum up values of all under nodes. |
    //+-----------------------------------+
    int sumNodes(TreeNode* n) {
        if (n == nullptr)return 0;
        return n->val + sumNodes(n->left) + sumNodes(n->right);
    }

    //+----------------+
    //| Scan Tree Node |
    //+----------------+
    //pre order
    Vi preOrder;
    void preOrderScan(TreeNode* n) {
        if (n == nullptr)return;
        preOrder.push_back(n->val);
        preOrderScan(n->left);
        preOrderScan(n->right);
    }
    //in order
    Vi inOrder;
    void inOrderScan(TreeNode* n) {
        if (n == nullptr)return;
        inOrderScan(n->left);
        inOrder.push_back(n->val);
        inOrderScan(n->right);
    }
    //post order Binary Tree
    Vi postOrder;
    void postOrderScan(TreeNode* n) {
        if (n == nullptr)return;
        postOrderScan(n->left);
        postOrderScan(n->right);
        postOrder.push_back(n->val);
    }
    //pre order Node which has children.
    Vi ans;
    Vi preorder(Node* n) {
        if (n == nullptr) return ans;
        ans.push_back(n->val);
        rep(i, 0, n->children.size()) preorder(n->children[i]);
        return ans;
    }
    //post order Node which has children.
    //vector<int> ans;
    //vector<int> postorder(Node* n) {
    //  if (n == nullptr) return ans;
    //  rep(i, 0, n->children.size()) postorder(n->children[i]);
    //  ans.push_back(n->val);
    //  return ans;
    //}

    //+---------------------------------------+
    //| Lowest Common Ancestor on Binary Tree |
    //+---------------------------------------+
    TreeNode* lowestCommonAncestor(TreeNode* n, TreeNode* p, TreeNode* q) {
        if (n == nullptr)return n;
        if (n->val > p->val && n->val > q->val) return lowestCommonAncestor(n->left, p, q);
        else if (n->val < p->val && n->val < q->val) return lowestCommonAncestor(n->right, p, q);
        return n;
    }

    //+--------------------+
    //| check if same tree |
    //+--------------------+
    bool isSameTree(TreeNode* t, TreeNode* s) {
        if (t == nullptr && s == nullptr) return true;
        if (t == nullptr || s == nullptr) return false;
        if (t->val != s->val) return false;
        return isSameTree(t->left, s->left) && isSameTree(t->right, s->right);
    }

    //+-----------------------+
    //| construct merged tree |
    //+-----------------------+
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr && t2 == nullptr) return t1;
        else if (t1 != nullptr && t2 != nullptr) {
            t1->val += t2->val;
        }
        else if (t1 != nullptr && t2 == nullptr) {
            return t1;
        }
        else if (t1 == nullptr && t2 != nullptr) {
            return t2;
        }

        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);

        return t1;
    }

    //+-------------------------+
    //| construct inverted tree |
    //+-------------------------+
    TreeNode* p;
    void invert_dfs(TreeNode* n, TreeNode* p) {
        if (n->right != nullptr) {
            p->left = new TreeNode(n->right->val);
            invert_dfs(n->right, p->left);
        }
        if (n->left != nullptr) {
            p->right = new TreeNode(n->left->val);
            invert_dfs(n->left, p->right);
        }
    }

    TreeNode* invertTree(TreeNode* n) {
        if (n == nullptr)return n;
        p = new TreeNode(n->val);
        invert_dfs(n, p);
        return p;
    }


    //+------------------+
    //| Trim Binary tree |
    //+------------------+
    TreeNode* trimBST(TreeNode* n, int L, int R) {
        if (n == nullptr) return n;

        if (n->val < L) {
            n = trimBST(n->right, L, R);
        }
        else if (n->val > R) {
            n = trimBST(n->left, L, R);
        }
        else {
            n->left = trimBST(n->left, L, R);
            n->right = trimBST(n->right, L, R);
        }

        return n;
    }

    //+-------------------------+
    //| construct BST by vector |
    //+-------------------------+
    TreeNode* constructBST(vector<int>& v, int l, int r) {
        int m = (l + r) / 2;
        TreeNode* p = new TreeNode(v[m]);
        if (l != r) {
            if (m != l) p->left = constructBST(v, l, m - 1);
            if (m != r) p->right = constructBST(v, m + 1, r);
        }
        return p;
    }
    TreeNode* sortedArrayToBST(vector<int>& v) {
        if (v.size() == 0)return nullptr;
        return constructBST(v, 0, v.size() - 1);
    }
};