Binary Trees HT #3
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
int data;
struct TreeNode* left;
struct TreeNode* right;
TreeNode(int val){
data = val;
left = right = NULL;
}
};
TreeNode* makeTree(vector<int> arr, int i){
if(i >= arr.size()) return NULL;
TreeNode* root = new TreeNode(arr[i]);
root->left = makeTree(arr, 2*i+1);
root->right = makeTree(arr, 2*i+2);
return root;
}
void printTree_PRE(TreeNode* root){
if(root == NULL) return;
// preorder: root, left, right
cout << root->data << " ";
printTree_PRE(root->left);
printTree_PRE(root->right);
}
void printTree_IN(TreeNode* root){
if(root == NULL) return;
// preorder: left, root, right
printTree_IN(root->left);
cout << root->data << " ";
printTree_IN(root->right);
}
void printTree_POST(TreeNode* root){
if(root == NULL) return;
// preorder: left, right, root
printTree_POST(root->left);
printTree_POST(root->right);
cout << root->data << " ";
}
// void levelOrder(TreeNode* root, queue<TreeNode*> &q){
// if(root == NULL || q.empty()) return;
// cout << q.front()->data << " ";
// TreeNode* node = q.front();
// q.pop();
// q.push(node->left);
// q.push(node->right);
// if(q.front()) levelOrder(node, q);
// }
void subBfs(vector<int> &ans, queue<TreeNode*> &q){
if(q.empty()) return;
TreeNode* temp = q.front();
q.pop();
ans.push_back(temp->data);
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
subBfs(ans, q);
return;
}
vector<int> levelOrder(TreeNode* root){
vector<int> ans;
if(root==NULL) return ans;
queue<TreeNode*> q;
q.push(root);
subBfs(ans, q);
return ans;
}
int treeHeight(TreeNode* root){
if(root == NULL) return 0;
int left = treeHeight(root->left);
int right = treeHeight(root->right);
return max(left, right) + 1;
}
int treeDiameter(TreeNode* root){
if(root== NULL) return 0;
// 1. height_left + height_right + 1(root)
// 2. maxdiameter at left or right
// calculate the tree height from both sides and then return height_left + height_right + 1
int leftHeight = treeHeight(root->left);
int rightHeight = treeHeight(root->right);
int leftDiameter = treeDiameter(root->left);
int rightDiameter = treeDiameter(root->right);
return max(leftHeight+rightHeight+1, max(leftDiameter, rightDiameter));
// TC: O(N*height)
}
pair<int,int> heightDiameter(TreeNode* root){
if(root==NULL){
pair<int,int> p;
p.first = p.second = 0;
return p;
}
pair<int,int> leftAns = heightDiameter(root->left);
pair<int,int> rightAns = heightDiameter(root->right);
int lh = leftAns.first;
int ld = leftAns.second;
int rh = rightAns.first;
int rd = rightAns.second;
pair<int,int> p;
p.first = 1 + max(lh, rh);
p.second = max(lh+rh+1, max(ld, rd));
return p;
// TC = O(N)
}
// shortest distance between root and a leaf:
// if anyone left or right is NULL then return !null only because shortest path != 0 until both right and left == NULL.
int minDepth(TreeNode* root) {
if(!root) return 0;
if(root->right == NULL && root->left != NULL){
return minDepth(root->left) + 1;
}
else if(root->left == NULL && root->right != NULL){
return minDepth(root->right) + 1;
}
else return min(minDepth(root->right), minDepth(root->left)) + 1;
}
int solve(TreeNode* root){
if(!root) return 0;
// pass: l + r + data
// take: l + r
int temp = root->val;
int l = solve(root->left);
int r = solve(root->right);
root->val = l + r;
return l + r + temp;
}
void toSumTree(TreeNode* root){
solve(root);
}
int main(){
// makeTree() use number of elements = 1 3 7 15 (2**h - 1)
// driver code
TreeNode* root = makeTree({1,2,3, 4,5,6,7}, 0);
// 1
// 2 3
// 4 5 6 7
// printTree_PRE(root);
return 0;
}
Comments
Post a Comment