Posts published in “Tree”

花花酱 LeetCode 987. Vertical Order Traversal of a Binary Tree

By zxi on February 2, 2019

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

Note:

The tree will have between 1 and 1000 nodes.
Each node’s value will be between 0 and 1000.

Solution: Ordered Map+ Ordered Set

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua, running time: 0 ms, 921.6 KB

class Solution {

public:

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

if (!root) return {};

int min_x = INT_MAX;

int max_x = INT_MIN;

map<pair<int, int>, multiset<int>> h; // {y, x} -> {vals}

traverse(root, 0, 0, h, min_x, max_x);

vector<vector<int>> ans(max_x - min_x + 1);

for (const auto& m : h) {

int x = m.first.second - min_x;

ans[x].insert(end(ans[x]), begin(m.second), end(m.second));

}

return ans;

}

private:

void traverse(TreeNode* root, int x, int y,

map<pair<int, int>, multiset<int>>& h,

int& min_x,

int& max_x) {

if (!root) return;

min_x = min(min_x, x);

max_x = max(max_x, x);

h[{y, x}].insert(root->val);

traverse(root->left, x - 1, y + 1, h, min_x, max_x);

traverse(root->right, x + 1, y + 1, h, min_x, max_x);

}

};

Python3

# Author: Huahua, 36 ms, 6.8 MB

class Solution:

def verticalTraversal(self, root: 'TreeNode') -> 'List[List[int]]':

if not root: return []

vals = []

def preorder(root, x, y):

if not root: return

vals.append((x, y, root.val))

preorder(root.left, x - 1, y + 1)

preorder(root.right, x + 1, y + 1)

preorder(root, 0, 0)

ans = []

last_x = -1000

for x, y, val in sorted(vals):

if x != last_x:

ans.append([])

last_x = x

ans[-1].append(val)

return ans

花花酱 LeetCode 979. Distribute Coins in Binary Tree

By zxi on January 20, 2019

Given the root of a binary tree with N nodes, each node in the tree has node.valcoins, and there are N coins total.

In one move, we may choose two adjacent nodes and move one coin from one node to another. (The move may be from parent to child, or from child to parent.)

Return the number of moves required to make every node have exactly one coin.

Example 1:

Input: [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves].  Then, we move one coin from the root of the tree to the right child.

Example 3:

Input: [1,0,2]
Output: 2

Example 4:

Input: [1,0,0,null,3]
Output: 4

Note:

1<= N <= 100
0 <= node.val <= N

Solution: Recursion

Compute the balance of left/right subtree, ans += abs(balance(left)) + abs(balance(right))
balance(root) = balance(left) + balance(right) + root.val – 1

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

int distributeCoins(TreeNode* root) {

int ans = 0;

balance(root, ans);

return ans;

}

private:

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

if (!root) return 0;

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

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

ans += abs(l) + abs(r);

return l + r + root->val - 1;

}

};

花花酱 LeetCode 971. Flip Binary Tree To Match Preorder Traversal

By zxi on January 5, 2019

Given a binary tree with N nodes, each node has a different value from {1, ..., N}.

A node in this binary tree can be flipped by swapping the left child and the right child of that node.

Consider the sequence of N values reported by a preorder traversal starting from the root. Call such a sequence of N values the voyage of the tree.

(Recall that a preorder traversal of a node means we report the current node’s value, then preorder-traverse the left child, then preorder-traverse the right child.)

Our goal is to flip the least number of nodes in the tree so that the voyage of the tree matches the voyagewe are given.

If we can do so, then return a list of the values of all nodes flipped. You may return the answer in any order.

If we cannot do so, then return the list [-1].

Example 1:

Input: root = [1,2], voyage = [2,1]
Output: [-1]

Example 2:

Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]

Example 3:

Input: root = [1,2,3], voyage = [1,2,3]
Output: []

Note:

1 <= N <= 100

Solution: Pre-order traversal

if root->val != v[pos] return [-1]
if root->left?->val != v[pos + 1], swap the nodes

c++

class Solution {

public:

vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {

vector<int> flips;

int pos = 0;

solve(root, voyage, pos, flips);

return flips;

}

private:

void solve(TreeNode* root, const vector<int>& voyage, int& pos, vector<int>& flips) {

if (!root) return;

if (root->val != voyage.at(pos)) {

flips.clear();

flips.push_back(-1);

return;

}

if (root->left && root->left->val != voyage.at(pos + 1)) {

swap(root->left, root->right);

flips.push_back(root->val);

}

++pos;

solve(root->left, voyage, pos, flips);

solve(root->right, voyage, pos, flips);

}

};

Python3

# Author: Huahua, 60 ms

class Solution:

def flipMatchVoyage(self, root, voyage):

self.pos = 0

self.flips = []

def solve(root):

if not root: return

if root.val != voyage[self.pos]:

self.flips = [-1]

return

if root.left and root.left.val != voyage[self.pos + 1]:

root.left, root.right = root.right, root.left

self.flips.append(root.val)

self.pos += 1

solve(root.left)

solve(root.right)

solve(root)

return self.flips

花花酱 LeetCode 968. Binary Tree Cameras

By zxi on December 31, 2018

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

The number of nodes in the given tree will be in the range [1, 1000].
Every node has value 0.

Solution: Greedy + Recursion

Time complexity: O(n)
Space complexity: O(h)

C++

enum class State { NONE = 0, COVERED = 1, CAMERA = 2 };

class Solution {

public:

int minCameraCover(TreeNode* root) {

if (dfs(root) == State::NONE) ++ans_;

return ans_;

}

private:

int ans_ = 0;

State dfs(TreeNode* root) {

if (!root) return State::COVERED;

State l = dfs(root->left);

State r = dfs(root->right);

if (l == State::NONE || r == State::NONE) {

++ans_;

return State::CAMERA;

}

if (l == State::CAMERA || r == State::CAMERA)

return State::COVERED;

return State::NONE;

}

};

花花酱 LeetCode 965. Univalued Binary Tree

By zxi on December 30, 2018

Problem

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1:

Input: [1,1,1,1,1,null,1]
Output: true

Example 2:

Input: [2,2,2,5,2]
Output: false

Note:

The number of nodes in the given tree will be in the range [1, 100].
Each node’s value will be an integer in the range [0, 99].

Solution: Recursion

Time complexity: O(n)
Space complexity: O(h)

C++

// Author: Huahua, running time: 0 ms

class Solution {

public:

bool isUnivalTree(TreeNode* root) {

if (!root) return true;

if (root->left && root->val != root->left->val) return false;

if (root->right && root->val != root->right->val) return false;

return isUnivalTree(root->left) && isUnivalTree(root->right);

}

};

Python3

# Author: Huahua, running time: 68 ms

class Solution:

def isUnivalTree(self, root):

if not root: return True

if root.left and root.left.val != root.val: return False

if root.right and root.right.val != root.val: return False

return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

Posts published in “Tree”

花花酱 LeetCode 987. Vertical Order Traversal of a Binary Tree

Solution: Ordered Map+ Ordered Set

C++

Python3

花花酱 LeetCode 979. Distribute Coins in Binary Tree

Solution: Recursion

C++

花花酱 LeetCode 971. Flip Binary Tree To Match Preorder Traversal

Solution: Pre-order traversal

c++

Python3

花花酱 LeetCode 968. Binary Tree Cameras

Solution: Greedy + Recursion

C++

花花酱 LeetCode 965. Univalued Binary Tree

Problem

Solution: Recursion

C++

Python3

Related Problems