Leetcode Binary Tree 用の関数一覧

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);
	}
};