Posts published in “Tree”

花花酱 LeetCode 98. Validate Binary Search Tree

By zxi on November 11, 2017

Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

/ \

1 3

Binary tree [2,1,3], return true.

Example 2:

/ \

2 3

Binary tree [1,2,3], return false.

Solution 1

Traverse the tree and limit the range of each subtree and check whether root’s value is in the range.

Time complexity: O(n)

Space complexity: O(n)

Note: in order to cover the range of -2^31 ~ 2^31-1, we need to use long or nullable integer.

C++/long

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, LLONG_MIN, LLONG_MAX);

}

private:

bool isValidBST(TreeNode* root, long min_val, long max_val) {

if (!root) return true;

if (root->val <= min_val || root->val >= max_val)

return false;

return isValidBST(root->left, min_val, root->val)

&& isValidBST(root->right, root->val, max_val);

}

};

C++/nullable

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, nullptr, nullptr);

}

private:

bool isValidBST(TreeNode* root, int* min_val, int* max_val) {

if (!root) return true;

if ((min_val && root->val <= *min_val)

||(max_val && root->val >= *max_val))

return false;

return isValidBST(root->left, min_val, &root->val)

&& isValidBST(root->right, &root->val, max_val);

}

};

Java/nullable

// Author: Huahua

// Running time: 1 ms

class Solution {

public boolean isValidBST(TreeNode root) {

return isValidBST(root, null, null);

}

private boolean isValidBST(TreeNode root, Integer min, Integer max) {

if (root == null) return true;

if ((min != null && root.val <= min)

||(max != null && root.val >= max))

return false;

return isValidBST(root.left, min, root.val)

&& isValidBST(root.right, root.val, max);

}

Solution 2

Do an in-order traversal, the numbers should be sorted, thus we only need to compare with the previous number.

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isValidBST(TreeNode* root) {

prev_ = nullptr;

return inOrder(root);

}

private:

TreeNode* prev_;

bool inOrder(TreeNode* root) {

if (!root) return true;

if (!inOrder(root->left)) return false;

if (prev_ && root->val <= prev_->val) return false;

prev_ = root;

return inOrder(root->right);

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

private TreeNode prev;

public boolean isValidBST(TreeNode root) {

prev = null;

return inOrder(root);

}

private boolean inOrder(TreeNode root) {

if (root == null) return true;

if (!inOrder(root.left)) return false;

if (prev != null && root.val <= prev.val) return false;

prev = root;

return inOrder(root.right);

}

Solution: Recursion

C++

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int maxPathSum(TreeNode* root) {

if (!root) return 0;

int ans = INT_MIN;

maxPathSum(root, ans);

return ans;

}

private:

int maxPathSum(TreeNode* root, int& ans) {

if (!root) return 0;

int l = max(0, maxPathSum(root->left, ans));

int r = max(0, maxPathSum(root->right, ans));

int sum = l + r + root->val;

ans = max(ans, sum);

return max(l, r) + root->val;

}

};

Python3

"""

Author: Huahua

Runtime: 138 ms (< 90.38%)

"""

class Solution(object):

def _maxPathSum(self, root):

if not root: return -sys.maxint

l = max(0, self._maxPathSum(root.left))

r = max(0, self._maxPathSum(root.right))

self.ans = max(self.ans, root.val + l + r)

return root.val + max(l, r)

def maxPathSum(self, root):

self.ans = -sys.maxint

self._maxPathSum(root)

return self.ans

Related Problems:

花花酱 LeetCode 543. Diameter of Binary Tree

By zxi on October 7, 2017

Problem:

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

/ \

2 3

/ \

4 5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Idea:

Recursion

Solution1:

C++

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

ans_ = 0;

LP(root);

return ans_;

}

private:

int ans_;

int LP(TreeNode* root) {

if (!root) return -1;

int l = LP(root->left) + 1;

int r = LP(root->right) + 1;

ans_ = max(ans_, l + r);

return max(l, r);

}

};

Solution 2: passed 101/106 TLE

C++ / Floyd-Warshall

// Author: Huahua

// State: 101/106 passed TLE

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

if (!root) return 0;

edges_.clear();

int n = 0;

buildGraph(root, n, -1);

vector<vector<int>> d(n, vector<int>(n, n));

for (int i = 0; i < n; ++i) d[i][i] = 0;

for (const auto& pair : edges_)

d[pair.first][pair.second] = 1;

for (int k = 0; k < n; ++k)

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j)

d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

int ans = INT_MIN;

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j) {

if (d[i][j] == n) continue;

ans = max(ans, d[i][j]);

}

return ans;

}

private:

void buildGraph(TreeNode* node, int& id, int pid) {

if (!node) return;

int node_id = id++;

if (pid >= 0) {

edges_.emplace_back(node_id, pid);

edges_.emplace_back(pid, node_id);

}

buildGraph(node->left, id, node_id);

buildGraph(node->right, id, node_id);

}

vector<pair<int,int>> edges_;

};

Solution 3:

Simulate recursion with a stack. We also need to track the return value of each node.

Python

"""

Author: Huahua

Runtime: 82 ms

"""

class Solution:

def diameterOfBinaryTree(self, root):

if not root: return 0

d = {None: -1}

s = [root]

ans = 0

while s:

node = s[-1]

if node.left in d and node.right in d:

s.pop()

l = d[node.left] + 1

r = d[node.right] + 1

ans = max(ans, l + r)

d[node] = max(l, r)

else:

if node.left: s.append(node.left)

if node.right: s.append(node.right)

return ans

C++

// Author: Huahua

// Runtime: 15 ms

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

if (!root) return 0;

int ans = 0;

unordered_map<TreeNode*, int> d{{nullptr, -1}};

stack<TreeNode*> s;

s.push(root);

while (!s.empty()) {

TreeNode* node = s.top();

if (d.count(node->left) && d.count(node->right)) {

int l = d[node->left] + 1;

int r = d[node->right] + 1;

ans = max(ans, l + r);

d[node] = max(l, r);

// children's results will never be used again, safe to delete here.

if (node->left) d.erase(node->left);

if (node->right) d.erase(node->right);

s.pop();

} else {

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

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

}

return ans;

}

};

Related Problems:

花花酱 LeetCode 687. Longest Univalue Path

By zxi on October 1, 2017

题目大意：给你一棵二叉树，返回一条最长的路径，要求路径上所有的节点值都相同。

https://leetcode.com/problems/longest-univalue-path/description/

Problem:

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

Output:

Example 2:

Input:

Output:

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

Idea:

DFS

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Runtime: 69 ms

class Solution {

public:

int longestUnivaluePath(TreeNode* root) {

if (root == nullptr) return 0;

int ans = 0;

univaluePath(root, &ans);

return ans;

}

private:

int univaluePath(TreeNode* root, int* ans) {

if (root == nullptr) return 0;

int l = univaluePath(root->left, ans);

int r = univaluePath(root->right, ans);

int pl = 0;

int pr = 0;

if (root->left && root->val == root->left->val) pl = l + 1;

if (root->right && root->val == root->right->val) pr = r + 1;

*ans = max(*ans, pl + pr);

return max(pl, pr);

}

};

Java

// Author: Huahua

// Runtime: 12 ms

class Solution {

private int ans;

public int longestUnivaluePath(TreeNode root) {

if (root == null) return 0;

this.ans = 0;

univaluePath(root);

return this.ans;

}

private int univaluePath(TreeNode root) {

if (root == null) return 0;

int l = univaluePath(root.left);

int r = univaluePath(root.right);

int pl = 0;

int pr = 0;

if (root.left != null && root.val == root.left.val) pl = l + 1;

if (root.right != null && root.val == root.right.val) pr = r + 1;

this.ans = Math.max(this.ans, pl + pr);

return Math.max(pl, pr);

}

Python3

"""

Author: Huahua

Runtime: 899 ms

"""

class Solution:

def longestUnivaluePath(self, root):

self.ans = 0

self._univaluePath(root)

return self.ans

def _univaluePath(self, root):

if root is None: return 0

l = self._univaluePath(root.left) if root.left is not None else -1

r = self._univaluePath(root.right) if root.right is not None else -1

pl = l + 1 if l >= 0 and root.val == root.left.val else 0

pr = r + 1 if r >= 0 and root.val == root.right.val else 0

self.ans = max(self.ans, pl + pr)

return max(pl, pr)

Posts published in “Tree”

花花酱 LeetCode 98. Validate Binary Search Tree

Solution 1

C++/long

C++/nullable

Java/nullable

Solution 2

C++

Java

Related Problem

花花酱 LeetCode 449. Serialize and Deserialize BST

花花酱 LeetCode 124. Binary Tree Maximum Path Sum

Solution: Recursion

C++

Python3

花花酱 LeetCode 543. Diameter of Binary Tree

花花酱 LeetCode 687. Longest Univalue Path

Solution: Recursion

C++

Java

Python3

Related Problems