花花酱 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);

}

};

花花酱 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

花花酱 Leetcode 100. Same Tree

By zxi on September 2, 2017

Problem:

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool isSameTree(TreeNode* p, TreeNode* q) {

// Both are emtry: same

if (!p && !q) return true;

// One is emtry: not the Same

if (!p || !q) return false;

// Both are not emptry, compare the root value

if (p->val != q->val) return false;

// Compare left-subtree and right-subtree recursively.

return isSameTree(p->left, q->left)

&& isSameTree(p->right, q->right);

}

};

Java

// Author: Huahua

class Solution {

public boolean isSameTree(TreeNode p, TreeNode q) {

if (p == null && q == null) return true;

if (p == null || q == null) return false;

return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

}

Python3

"""

Author: Huahua

"""

class Solution:

def isSameTree(self, p, q):

if not p and not q: return True

if not p or not q: return False

return all((p.val == q.val,

self.isSameTree(p.left, q.left),

self.isSameTree(p.right, q.right)))

Follow Up

花花酱 LeetCode 572. Subtree of Another Tree

Posts published in “Tree”

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

花花酱 LeetCode 102. Binary Tree Level Order Traversal

花花酱 LeetCode 110. Balanced Binary Tree

花花酱 Leetcode 100. Same Tree

Problem:

Example 1:

Example 2:

Example 3:

Solution: Recursion

C++

Java

Python3

Follow Up