Posts tagged as “tree”

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

花花酱 LeetCode 958. Check Completeness of a Binary Tree

By zxi on December 18, 2018

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Example 1:

Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Note:

The tree will have between 1 and 100 nodes.

Solution:

Level order traversal, if any nodes appears after a missing node then the tree is not a perfect binary tree.

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isCompleteTree(TreeNode* root) {

if (!root) return true;

queue<TreeNode> q;

q.push(root);

bool missing = false;

while (!q.empty()) {

auto size = q.size();

while (size--) {

auto node = q.front(); q.pop();

if (node) {

if (missing) return false;

q.push(node->left);

q.push(node->right);

} else {

missing = true;

}

return true;

}

};

Python3

class Solution:

def isCompleteTree(self, root):

if not root: return True

q = collections.deque([root])

missing = False

while q:

size = len(q)

while size > 0:

size -= 1

node = q.popleft()

if node:

if missing: return False

q.append(node.left)

q.append(node.right)

else:

missing = True

return True

Posts tagged as “tree”

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

花花酱 LeetCode 958. Check Completeness of a Binary Tree

Solution:

C++

Python3