binary tree – Page 2 – Huahua’s Tech Road

花花酱 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 669. Trim a Binary Search Tree

花花酱 LeetCode 102. Binary Tree Level Order Traversal

花花酱 LeetCode 110. Balanced Binary Tree