binary tree Archives - Page 2 of 2

花花酱 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 102. Binary Tree Level Order Traversal

By zxi on September 4, 2017

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

/ \

9 20

/ \

15 7

return its level order traversal as:

[

[3],

[9,20],

[15,7]

]

Solution 1: BFS O(n)

class Solution {

public:

vector<vector<int>> levelOrder(TreeNode* root) {

if(!root) return {};

vector<vector<int>> ans;

vector<TreeNode*> curr,next;

curr.push_back(root);

while(!curr.empty()) {

ans.push_back({});

for(TreeNode* node : curr) {

ans.back().push_back(node->val);

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

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

}

curr.swap(next);

next.clear();

}

return ans;

}

};

Solution 2: DFS O(n)

class Solution {

public:

vector<vector<int>> levelOrder(TreeNode* root) {

vector<vector<int>> ans;

DFS(root, 0 /* depth */, ans);

return ans;

}

private:

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

if(!root) return;

// Works with pre/in/post order

while(ans.size()<=depth) ans.push_back({});

ans[depth].push_back(root->val); // pre-order

DFS(root->left, depth+1, ans);

DFS(root->right, depth+1, ans);

}

};

花花酱 LeetCode 110. Balanced Binary Tree

By zxi on September 3, 2017

Solution 1: O(nlogn)

// Author: Huahua

// O(nlogn)

class Solution {

Solution 1: O(nlogn)

public:

bool isBalanced(TreeNode* root) {

if(!root) return true;

int left_height = height(root->left);

int right_height = height(root->right);

return (abs(left_height - right_height)<=1) && isBalanced(root->left) && isBalanced(root->right);

}

private:

int height(TreeNode* root) {

if(!root) return 0;

return max(height(root->left), height(root->right))+1;

}

};

Solution 2: O(n)

// Author: Huahua

// O(n)

class Solution {

public:

bool isBalanced(TreeNode* root) {

if(!root) return true;

bool balanced = true;

height(root, &balanced);

return balanced;

}

private:

int height(TreeNode* root, bool* balanced) {

if(!root) return 0;

int left_height = height(root->left, balanced);

if(!balanced) return -1;

int right_height = height(root->right, balanced);

if(!balanced) return -1;

if(abs(left_height-right_height)>1) {

*balanced = false;

return -1;

}

return max(left_height, right_height) + 1;

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

private boolean balanced;

private int height(TreeNode root) {

if (root == null || !this.balanced) return -1;

int l = height(root.left);

int r = height(root.right);

if (Math.abs(l - r) > 1) {

this.balanced = false;

return -1;

}

return Math.max(l, r) + 1;

}

public boolean isBalanced(TreeNode root) {

this.balanced = true;

height(root);

return this.balanced;

}

Python

"""

Author: Huahua

Running time: 76 ms

"""

class Solution:

def isBalanced(self, root):

self.balanced = True

def height(root):

if not root or not self.balanced: return -1

l = height(root.left)

r = height(root.right)

if abs(l - r) > 1:

self.balanced = False

return -1

return max(l, r) + 1

height(root)

return self.balanced

Posts tagged as “binary tree”

花花酱 LeetCode 654. Maximum Binary Tree

花花酱 LeetCode 669. Trim a Binary Search Tree

花花酱 LeetCode 102. Binary Tree Level Order Traversal

花花酱 LeetCode 110. Balanced Binary Tree