データ構造とアルゴリズム---ツリー関連テーマ
83036 ワード
再帰する
1.二叉サーチツリーと双方向リンク表
一本の二叉検索ツリーを入力して、二叉検索ツリーを並べ替えた双方向チェーンテーブルです.任意の新しい結点を作成することができず、ツリー内の結点ポインタの方向を調整するしかないことを要求します.
二叉の木の前の順序と中の順序が巡回した結果を入力して、二叉の木を再構築してください.入力された前の順序と中の順序を巡回した結果には重複した数字が含まれていないと仮定します.例えば、シーケンス｛1,2,4,7,3,5,6,8｝と中順序巡回シーケンス｛4,7,2,1,5,3,8,6｝を入力すると、二叉ツリーを再構築して戻ります.
二本の二叉樹Aを入力して、BはAのサブ構造であるかどうかを判断します.(ps:空の木は任意の木のサブ構造ではないと約束しました.)
一本の二叉の木を入力して、この木の深さを求めます.ルートの結点から葉の結点まで順次通る結点(根、葉の結点をくわえます)は木の1本のパスを形成して、最も長いパスの長さは木の深さです.
二つの二叉の木を与えられました.それらの中の一つを別の上に覆うと、二つの二叉の木の一部のノードが重なり合うと想像します.彼らを新しい二叉の木に合併する必要があります.統合のルールは、2つのノードが重ならば、それらの値をノードマージ後の新しい値として加算し、NULLでないノードは、直接に新しい2つのツリーのノードとして作用する.
二叉樹と一つの目標とを与え、このツリーにルートノードからリーフノードまでの経路があるかどうかを判断する.この経路における全てのノード値の加算は目標和に等しい.
7.2パス合計
二叉の木を与えられました.各結点には整数値が格納されています.指定された値に等しいパスの総数を検索します.ルートはルートノードから開始する必要もないし、リーフノードで終了する必要もないが、経路方向は下向きでなければならない(親ノードからサブノードまで).二叉樹は1000個のノードを超えず、ノードの数値範囲は「-100000,100000」の整数です.
二叉の木を与えて、それが鏡像対称であるかどうかを確認します.
例えば、二叉樹[1,2,2,3,4,4,3]は対称である.しかし[1,2,2,null,3,null,3]は鏡像対称ではありません.
二叉の木を与えて、その最小深さを探し出します.最小深度はルートノードから一番近いリーフノードまでの最短経路のノード数である.https://leetcode.com/problems/minimum-depth-of-binary-tree/
与えられた二叉樹の左葉の合計を計算します.https://leetcode.com/problems/sum-of-left-leaves/description/
BFSを使用してレベルを巡回します.各レイヤーのノード数をメモして、1つのキューで各レイヤーの出力を完了します.
11.ツリーの各層のノードの平均数
Gven a non-empty binary tree、return the average value of the nodes on each level in the form of an array.https://leetcode.com/problems/average-of-levels-in-binary-tree/
Gven a non-empty binary tree、return the average value of the nodes on each level in the form of an array.https://leetcode.com/problems/average-of-levels-in-binary-tree/
BST
13.BSTのトリミング
Given a binary search tree and the lowest and highest boundaries as L and R,trim the tree so that all its elemens lies in[L,R](R>=L)You might need to change the root of the tree,so the metrouryhttps://leetcode.com/problems/trim-a-binary-search-tree/
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
Gven a Binary Search Tree(BST)、convert it to a Greter Tree such that everkey of the original BST is changed to the orriginal key plus sum of all keys greater than the original key in BST.https://leetcode.com/problems/convert-bst-to-greater-tree/
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
18.順序配列から二叉ルックアップツリーを構築する
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
20.二叉ルックアップツリーでは、二つのノードを探して、それらの和を所与の値にします.
https://leetcode.com/problems/two-sum-iv-input-is-a-bst/巡回した値をsetに入れて、target-現在のノード値がsetにあるかどうか調べます.
21.再帰前の順序ではなく、二叉の木を巡回します.
前の順序はroot->left->Rightで、スタックの順序はroot->right->leftで、後の順序はleft->Right->rootで、もしスタックの順序がroot->leftであれば、出力の順序はroot->Right->leftであり、この順序はちょうど後の順序と逆になります.
23.再帰的でない中間順序を巡回する
1.二叉サーチツリーと双方向リンク表
一本の二叉検索ツリーを入力して、二叉検索ツリーを並べ替えた双方向チェーンテーブルです.任意の新しい結点を作成することができず、ツリー内の結点ポインタの方向を調整するしかないことを要求します.
TreeNode* Convert(TreeNode* pRootOfTree)
{
// null
if(pRootOfTree==nullptr)
return nullptr;
//
if(pRootOfTree->left==nullptr && pRootOfTree->right==nullptr)
return pRootOfTree;
//
TreeNode* leftHead = Convert(pRootOfTree->left);
TreeNode* rightHead = Convert(pRootOfTree->right);
//
TreeNode* tmp = leftHead;
while(tmp!=nullptr && tmp->right!=nullptr){
tmp = tmp->right;
}
// ，
if(leftHead != nullptr){
tmp->right = pRootOfTree;
pRootOfTree->left = tmp;
}
// ，
if(rightHead!=nullptr){
pRootOfTree->right = rightHead;
rightHead->left = pRootOfTree;
}
//
return leftHead==nullptr ? pRootOfTree:leftHead;
}
二叉の木の前の順序と中の順序が巡回した結果を入力して、二叉の木を再構築してください.入力された前の順序と中の順序を巡回した結果には重複した数字が含まれていないと仮定します.例えば、シーケンス｛1,2,4,7,3,5,6,8｝と中順序巡回シーケンス｛4,7,2,1,5,3,8,6｝を入力すると、二叉ツリーを再構築して戻ります.
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
int length = vin.size();
if(length==0)
return nullptr;
struct TreeNode *head = new struct TreeNode(pre[0]);
int rootindex = 0;
vector<int> pre_left,pre_right,vin_left,vin_right;
for(int i=0;i<length;++i){
if(vin[i] == pre[0]){
rootindex = i;
break;
}
}
for(int i=0;i<rootindex;++i){
pre_left.push_back(pre[i+1]);
vin_left.push_back(vin[i]);
}
for(int i=rootindex+1;i<length;++i){
pre_right.push_back(pre[i]);
vin_right.push_back(vin[i]);
}
head->left = reConstructBinaryTree(pre_left,vin_left);
head->right = reConstructBinaryTree(pre_right,vin_right);
return head;
}
二本の二叉樹Aを入力して、BはAのサブ構造であるかどうかを判断します.(ps:空の木は任意の木のサブ構造ではないと約束しました.)
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot2==nullptr || pRoot1==nullptr) //
return false;
TreeNode *tmp = nullptr;
queue<TreeNode*> q;
q.push(pRoot1);
while(!q.empty()){ //
tmp = q.front();
q.pop();
if(doesT1HaveT2(tmp,pRoot2)) // tmp pRoot2
return true;
if(tmp->left)
q.push(tmp->left);
if(tmp->right)
q.push(tmp->right);
}
return false;
};
/* A R B ， ：
R B ， R B ，
， ； A
B (R ） */
bool doesT1HaveT2(TreeNode* p1, TreeNode* p2){
if(p2 == nullptr) // B A R B
return true;
if(p1 == nullptr) // B A A
return false; // B
if(p1->val != p2->val)
return false;
return doesT1HaveT2(p1->left,p2->left) && doesT1HaveT2(p1->right,p2->right);
}
一本の二叉の木を入力して、この木の深さを求めます.ルートの結点から葉の結点まで順次通る結点(根、葉の結点をくわえます)は木の1本のパスを形成して、最も長いパスの長さは木の深さです.
int maxDepth(TreeNode* root) {
if(root==nullptr)
return 0;
int leftD = maxDepth(root->left);
int rightD = maxDepth(root->right);
return leftD>rightD ? leftD+1:rightD+1;
}
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr)
return nullptr;
if(root->left==nullptr && root->right==nullptr)
return root;
TreeNode *left = invertTree(root->left);
TreeNode *right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
二つの二叉の木を与えられました.それらの中の一つを別の上に覆うと、二つの二叉の木の一部のノードが重なり合うと想像します.彼らを新しい二叉の木に合併する必要があります.統合のルールは、2つのノードが重ならば、それらの値をノードマージ後の新しい値として加算し、NULLでないノードは、直接に新しい2つのツリーのノードとして作用する.
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if(t1==nullptr && t2==nullptr)
return nullptr;
if(t1==nullptr)
return t2;
if(t2==nullptr)
return t1;
TreeNode *root = new TreeNode(t1->val+t2->val);
root->left = mergeTrees(t1->left,t2->left);
root->right = mergeTrees(t1->right,t2->right);
return root;
}
二叉樹と一つの目標とを与え、このツリーにルートノードからリーフノードまでの経路があるかどうかを判断する.この経路における全てのノード値の加算は目標和に等しい.
bool hasPathSum(TreeNode* root, int sum) {
if(root==nullptr)
return false;
if((root->left == nullptr) && (root->right == nullptr)){
if(sum == root->val)
return true;
}
return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
}
7.2パス合計
二叉の木を与えられました.各結点には整数値が格納されています.指定された値に等しいパスの総数を検索します.ルートはルートノードから開始する必要もないし、リーフノードで終了する必要もないが、経路方向は下向きでなければならない(親ノードからサブノードまで).二叉樹は1000個のノードを超えず、ノードの数値範囲は「-100000,100000」の整数です.
int pathSum(TreeNode* root, int sum) {
if(root==nullptr)
return 0;
int ret = pathSumRoot(root,sum) + pathSum(root->left,sum) + pathSum(root->right,sum);
return ret;
}
int pathSumRoot(TreeNode *root,int sum){
if(root==nullptr)
return 0;
int ret = 0;
if(root->val==sum) ret++;
ret += pathSumRoot(root->left,sum-root->val) + pathSumRoot(root->right,sum-root->val);
return ret;
}
二叉の木を与えて、それが鏡像対称であるかどうかを確認します.
例えば、二叉樹[1,2,2,3,4,4,3]は対称である.しかし[1,2,2,null,3,null,3]は鏡像対称ではありません.
bool isSymmetric(TreeNode* root) {
if(root==nullptr) return true;
return isSymmetric(root->left,root->right);
}
bool isSymmetric(TreeNode *left,TreeNode *right){
if(left==nullptr && right==nullptr) return true;
if(left==nullptr || right==nullptr) return false;
if(left->val != right->val) return false;
return isSymmetric(left->left,right->right) && isSymmetric(left->right,right->left);
}
二叉の木を与えて、その最小深さを探し出します.最小深度はルートノードから一番近いリーフノードまでの最短経路のノード数である.https://leetcode.com/problems/minimum-depth-of-binary-tree/
int minDepth(TreeNode* root) {
if(root==nullptr) return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
if(left==0 || right==0) return left+right+1;
return min(left,right) + 1;
}
与えられた二叉樹の左葉の合計を計算します.https://leetcode.com/problems/sum-of-left-leaves/description/
int sumOfLeftLeaves(TreeNode* root) {
if(root==nullptr) return 0;
if(isLeaf(root->left)) return root->left->val + sumOfLeftLeaves(root->right);
return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
bool isLeaf(TreeNode *root){
if(root==nullptr) return false;
return root->left==nullptr && root->right==nullptr;
}
BFSを使用してレベルを巡回します.各レイヤーのノード数をメモして、1つのキューで各レイヤーの出力を完了します.
11.ツリーの各層のノードの平均数
Gven a non-empty binary tree、return the average value of the nodes on each level in the form of an array.https://leetcode.com/problems/average-of-levels-in-binary-tree/
vector<double> averageOfLevels(TreeNode* root) {
if(root==nullptr) return vector<double>(0);
queue<TreeNode*> q;
vector<double> v;
q.push(root);
int currentNum = 1;
int nextNum = 0;
double avg = 0.0;
while(!q.empty()){
nextNum = 0;
avg = 0;
int i = currentNum;
while(i){
TreeNode *tmp = q.front();
q.pop();
avg += tmp->val;
if(tmp->left!=nullptr){
q.push(tmp->left);
nextNum++;
}
if(tmp->right!=nullptr){
q.push(tmp->right);
nextNum++;
}
--i;
}
avg /= currentNum;
v.push_back(avg);
currentNum = nextNum;
}
return v;
}
Gven a non-empty binary tree、return the average value of the nodes on each level in the form of an array.https://leetcode.com/problems/average-of-levels-in-binary-tree/
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int num = q.size();
int i = num;
TreeNode *leftNode = nullptr;
while(i){
TreeNode *tmp = q.front();
q.pop();
if(i==num)
leftNode = tmp;
if(tmp->left!=nullptr) q.push(tmp->left);
if(tmp->right!=nullptr) q.push(tmp->right);
--i;
}
if(q.empty())
return leftNode->val;
}
return -1;
}
BST
13.BSTのトリミング
Given a binary search tree and the lowest and highest boundaries as L and R,trim the tree so that all its elemens lies in[L,R](R>=L)You might need to change the root of the tree,so the metrouryhttps://leetcode.com/problems/trim-a-binary-search-tree/
TreeNode* trimBST(TreeNode* root, int L, int R) {
if(root==nullptr) return nullptr;
if(root->val > R) return trimBST(root->left,L,R);
if(root->val < L) return trimBST(root->right,L,R);
root->left = trimBST(root->left,L,R);
root->right = trimBST(root->right,L,R);
return root;
}
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
preOrder(root,k);
return result;
}
void preOrder(TreeNode* root,int k){
if(root){
preOrder(root->left,k);
time++;
if(time==k){
result = root->val;
}
preOrder(root->right,k);
}
}
private:
int time=0; //
int result;
};
Gven a Binary Search Tree(BST)、convert it to a Greter Tree such that everkey of the original BST is changed to the orriginal key plus sum of all keys greater than the original key in BST.https://leetcode.com/problems/convert-bst-to-greater-tree/
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
inOrder(root);
return root;
}
void inOrder(TreeNode* root){
if(root){
inOrder(root->right);
root->val += sum;
sum = root->val;
inOrder(root->left);
}
}
private:
int sum=0;
};
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root->val > p->val && root->val > q->val){
return lowestCommonAncestor(root->left,p,q);
}
if(root->val < p->val && root->val < q->val){
return lowestCommonAncestor(root->right,p,q);
}
return root;
}
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
18.順序配列から二叉ルックアップツリーを構築する
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
TreeNode* sortedArrayToBST(vector<int>& nums) {
int size = nums.size();
if(size==0)
return nullptr;
int middle = (size-1)/2;
int middleVal = nums[middle];
TreeNode* node = new TreeNode(middleVal);
vector<int> leftnums(nums.begin(),nums.begin()+middle);
vector<int> rightnums(nums.begin()+middle+1,nums.end());
TreeNode* left = sortedArrayToBST(leftnums);
TreeNode* right = sortedArrayToBST(rightnums);
node->left = left;
node->right = right;
return node;
}
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
20.二叉ルックアップツリーでは、二つのノードを探して、それらの和を所与の値にします.
https://leetcode.com/problems/two-sum-iv-input-is-a-bst/巡回した値をsetに入れて、target-現在のノード値がsetにあるかどうか調べます.
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
traversal(root,k);
return ret;
}
void traversal(TreeNode* root,int k){
if(root){
traversal(root->left,k);
if(s.find(k-root->val) != s.end()){
ret = true;
return;
}
s.insert(root->val);
traversal(root->right,k);
}
}
private:
unordered_set<int> s;
bool ret=false;
};
21.再帰前の順序ではなく、二叉の木を巡回します.
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode* tmp = s.top();
s.pop();
if(tmp==nullptr) continue;
v.push_back(tmp->val);
s.push(tmp->right); //
s.push(tmp->left);
}
return v;
}
前の順序はroot->left->Rightで、スタックの順序はroot->right->leftで、後の順序はleft->Right->rootで、もしスタックの順序がroot->leftであれば、出力の順序はroot->Right->leftであり、この順序はちょうど後の順序と逆になります.
23.再帰的でない中間順序を巡回する
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
if(root==nullptr) return v;
stack<TreeNode*> s;
//s.push(root);
TreeNode* cur = root;
while(cur!=nullptr || !s.empty()){
while(cur!=nullptr){
s.push(cur);
cur = cur->left;
}
TreeNode* tmp = s.top();
s.pop();
v.push_back(tmp->val);
cur = tmp->right;
}
return v;
}