Posts published in “Tree”

花花酱 LeetCode 145. Binary Tree Postorder Traversal

By zxi on September 8, 2017

Problem:

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

vector<int> ans;

postorderTraversal(root, ans);

return ans;

}

void postorderTraversal(TreeNode* root, vector<int>& ans) {

if (!root) return;

postorderTraversal(root->left, ans);

postorderTraversal(root->right, ans);

ans.push_back(root->val);

}

};

Solution 2:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

vector<int> ans;

const vector<int> l = postorderTraversal(root->left);

const vector<int> r = postorderTraversal(root->right);

ans.insert(ans.end(), l.begin(), l.end());

ans.insert(ans.end(), r.begin(), r.end());

ans.push_back(root->val);

return ans;

}

};

Solution 3:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

deque<int> ans;

stack<TreeNode*> s;

s.push(root);

while (!s.empty()) {

TreeNode* n = s.top();

s.pop();

ans.push_front(n->val); // O(1)

if (n->left) s.push(n->left);

if (n->right) s.push(n->right);

}

return vector<int>(ans.begin(), ans.end());

}

};

花花酱 LeetCode 637. Average of Levels in Binary Tree

By zxi on September 7, 2017

Problem:

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Input:

/ \

9 20

/ \

15 7

Output: [3, 14.5, 11]

Explanation:

The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.

Hence return [3, 14.5, 11].

Time Complexity:

O(n)

Space Complexity:

O(h)

Solution 1:

BFS

// Author: Huahua

class Solution {

public:

vector<double> averageOfLevels(TreeNode* root) {

if(root == nullptr) return {};

vector<double> ans;

vector<TreeNode*> curr, next;

curr.push_back(root);

// process every level one by one

while(!curr.empty()) {

long long sum = 0;

for(const auto& node : curr) {

sum += node->val;

if (node->left) next.push_back(node->left);

if (node->right) next.push_back(node->right);

}

ans.push_back(static_cast<double>(sum) / curr.size());

curr.swap(next);

next.clear();

}

return ans;

}

};

Solution 2:

DFS

// Author: Huahua

class Solution {

public:

vector<double> averageOfLevels(TreeNode* root) {

if(root == nullptr) return {};

vector<pair<long long, int>> sum_count;

vector<double> ans;

preorder(root, 0, sum_count);

for(const auto& p : sum_count)

ans.push_back(static_cast<double>(p.first) / p.second);

return ans;

}

private:

void preorder(TreeNode* root, int depth, vector<pair<long long, int>>& sum_count) {

if(root == nullptr) return;

if(depth>=sum_count.size()) sum_count.push_back({0,0});

sum_count[depth].first += root->val;

++sum_count[depth].second;

preorder(root->left, depth+1, sum_count);

preorder(root->right, depth+1, sum_count);

}

};

Related Problems:

[解题报告] LeetCode 102. Binary Tree Level Order Traversal

花花酱 LeetCode 654. Maximum Binary Tree

By zxi on September 4, 2017

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]

Output: return the tree root node representing the following tree:

/ \

3 5

\ /

2 0

Idea:

Recursion

Solution:

With copy

Time complexity: O(nlogn) ~ O(n^2)

Space complexity: O(nlogn) ~ O(n^2)

running time 79ms

// Author: Huahua

class Solution {

public:

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

if(nums.empty()) return nullptr;

auto it = std::max_element(nums.begin(), nums.end());

TreeNode* root=new TreeNode(*it);

vector<int> left(nums.begin(), it);

vector<int> right(it+1, nums.end());

root->left = constructMaximumBinaryTree(left);

root->right = constructMaximumBinaryTree(right);

return root;

}

Without copy

Time complexity: O(nlogn) ~ O(n^2)

Space complexity: O(logn) ~ O(n)

running time 66ms

// Author: Huahua

class Solution {

public:

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

return makeMBT(nums, 0, nums.size());

}

private:

TreeNode* makeMBT(const vector<int>& nums, int begin, int end) {

if(begin>=end) return nullptr;

auto it = std::max_element(nums.begin() + begin, nums.begin() + end);

TreeNode* root=new TreeNode(*it);

int index = it - nums.begin();

root->left = makeMBT(nums, begin, index);

root->right = makeMBT(nums, index+1, end);

return root;

}

};

花花酱 LeetCode 669. Trim a Binary Search Tree

By zxi on September 4, 2017

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

Input:

/ \

0 2

L = 1

R = 2

Output:

Example 2:

Input:

/ \

0 4

L = 1

R = 3

Output:

This problem can be solved with recursion

There 3 cases in total depends on the root value and L, R

Time complexity: O(n)

Space complexity: O(1)

Solution:

// Author: Huahua

class Solution {

public:

// No cleanup -> memory leak

TreeNode* trimBST(TreeNode* root, int L, int R) {

if(!root) return nullptr;

// val not in range, return the left/right subtrees

if(root->val < L) return trimBST(root->right, L, R);

if(root->val > R) return trimBST(root->left, L, R);

// val in [L, R], recusively trim left/right subtrees

root->left = trimBST(root->left, L, R);

root->right = trimBST(root->right, L, R);

return root;

}

};

The previous solution has potential memory leak for languages without garbage collection.

Here’s the full program to delete trimmed nodes.

// Author: Huahua

#include <iostream>

using namespace std;

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

// With cleanup -> no memory leak

TreeNode*& trimBST(TreeNode*& root, int L, int R) {

if(!root) return root;

if(root->val < L) {

auto& result = trimBST(root->right, L, R);

deleteTree(root->left);

delete root;

root=nullptr;

return result;

} else if(root->val > R) {

auto& result = trimBST(root->left, L, R);

deleteTree(root->right);

delete root;

root=nullptr;

return result;

} else {

// recusively trim left/right subtrees

root->left = trimBST(root->left, L, R);

root->right = trimBST(root->right, L, R);

return root;

}

void deleteTree(TreeNode* &root) {

if(!root) return;

deleteTree(root->left);

deleteTree(root->right);

delete root;

root=nullptr;

}

};

void PrintTree(TreeNode* root) {

if(!root) {

cout<<"null ";

return;

};

if(!root->left && !root->right) {

cout<<root->val<<" ";

} else {

cout<<root->val<<" ";

PrintTree(root->left);

PrintTree(root->right);

}

int main()

{

TreeNode* root=new TreeNode(2);

root->left=new TreeNode(1);

root->right=new TreeNode(3);

PrintTree(root);

std::cout<<std::endl;

TreeNode* t = Solution().trimBST(root, 3, 4);

PrintTree(t);

std::cout<<std::endl;

// Original root was deleted

PrintTree(root);

std::cout<<std::endl;

return 0;

}

Example output

2 1 3

null

花花酱 LeetCode 671. Second Minimum Node In a Binary Tree

By zxi on September 4, 2017

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

Input:

/ \

2 5

/ \

5 7

Output: 5

Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input:

/ \

2 2

Output: -1

Explanation: The smallest value is 2, but there isn't any second smallest value.

Solution:

Time complexity O(n), Space complexity O(n)

/**

* 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:

int findSecondMinimumValue(TreeNode* root) {

if(!root) return -1;

// return BFS(root);

return DFS(root, root->val);

}

private:

// Time complexity: O(n)

// Space complexity: O(n)

int BFS(TreeNode* root) {

if(!root) return -1;

// Smallest value

int s1 = root->val;

// Sencond smallest value

int s2 = INT_MAX;

bool found = false;

deque<TreeNode*> q;

q.push_back(root);

while(!q.empty()) {

TreeNode* node = q.front();

q.pop_front();

// Keep updating second smallest value

if(node->val > s1 && node->val < s2) {

s2 = node->val;

found = true;

// No need to add it's children into queue

continue;

}

if(!node->left) continue;

q.push_back(node->left);

q.push_back(node->right);

}

return found?s2:-1;

}

// Return the second smallest number in the (sub-tree)

// s1 is the smallest value

int DFS(TreeNode* root, int s1) {

if(!root) return -1;

// If root's value is already grater than s1,

// then all its children's value should be >= s1.

// Thus root's value is the second smallest one.

// No need to visit the

if(root->val > s1) return root->val;

int sl = DFS(root->left, s1);

int sr = DFS(root->right, s1);

if(sl == -1) return sr;

if(sr == -1) return sl;

// Return the smaller one among two subtrees

return min(sl, sr);

}

};