Huahua’s Tech Road

花花酱 LeetCode 993. Cousins in Binary Tree

By zxi on February 16, 2019

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Note:

The number of nodes in the tree will be between 2 and 100.
Each node has a unique integer value from 1 to 100.

Solution: Preorder traversal

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

C++

// Author: Huahua, running time 8 ms, 11.5 MB

class Solution {

public:

bool isCousins(TreeNode* root, int x, int y) {

preorder(root, x, y, nullptr, 0);

return px_ != py_ && dx_ == dy_;

}

private:

TreeNode* px_;

TreeNode* py_;

int dx_;

int dy_;

void preorder(TreeNode* root, int x, int y, TreeNode* p, int d) {

if (!root) return;

if (root->val == x) {

px_ = p;

dx_ = d;

}

if (root->val == y) {

py_ = p;

dy_ = d;

}

preorder(root->left, x, y, root, d + 1);

preorder(root->right, x, y, root, d + 1);

}

};

Python3

# Author: Huahua, running time: 40 ms, 12.4 MB

class Solution:

def isCousins(self, root: 'TreeNode', x: 'int', y: 'int') -> 'bool':

self.px, self.dx = None, -1

self.py, self.dy = None, -2

def preorder(root, parent, d):

if not root: return

if root.val == x:

self.px, self.dx = parent, d

if root.val == y:

self.py, self.dy = parent, d

preorder(root.left, root, d + 1)

preorder(root.right, root, d + 1)

preorder(root, None, 0)

return self.dx == self.dy and self.px != self.py

LeetCode 进入千题时代该如何刷题？

By zxi on February 16, 2019

题目列表：https://bit.ly/2E8yBHq

总结一下：

大家的刷题经验都比我丰富，找到最适合自己的方法就好了
200～300题刷2-3边，至少100+小时的投入
同一类型题目一起刷，总结规律和差异
多看别人的（优秀）代码
完整的手写实现，不要copy代码，增强肌肉记忆（视频中没提到）
培养代码风格

花花酱 LeetCode 74. Search a 2D Matrix

By zxi on February 13, 2019

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:

matrix = [

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 3

Output: true

Example 2:

Input:

matrix = [

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 13

Output: false

Solution: Binary Search

Treat the 2D array as a 1D array. matrix[index / cols][index % cols]

Time complexity: O(log(m*n))
Space complexity: O(1)

C++

class Solution {

public:

bool searchMatrix(vector<vector<int>>& matrix, int target) {

if (matrix.empty()) return false;

int l = 0;

int r = matrix.size() * matrix[0].size();

const int cols = matrix[0].size();

while (l < r) {

const int m = l + (r - l) / 2;

if (matrix[m / cols][m % cols] == target) {

return true;

} else if (matrix[m / cols][m % cols] > target) {

r = m;

} else {

l = m + 1;

}

return false;

}

};

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.
OJ’s undirected graph serialization (so you can understand error output):

Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don’t need to understand the serialization to solve the problem.

Solution: Queue + Hashtable

Time complexity: O(V+E)
Space complexity: O(V+E)

C++

// Author: Huahua, 44ms, 16.8MB

class Solution {

public:

UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {

if (!node) return nullptr;

typedef UndirectedGraphNode Node;

unordered_set<Node*> done;

unordered_map<Node*, Node*> m;

queue<Node*> q;

q.push(node);

while (!q.empty()) {

Node* s = q.front(); q.pop();

if (done.count(s)) continue;

done.insert(s);

if (!m.count(s))

m[s] = new Node(s->label);

Node* t = m[s];

for (Node* ss : s->neighbors) {

if (!m.count(ss))

m[ss] = new Node(ss->label);

q.push(ss);

t->neighbors.push_back(m[ss]);

}

return m[node];

}

};

花花酱 LeetCode Weekly 123

By zxi on February 10, 2019

花花酱 LeetCode 993. Cousins in Binary Tree

Solution: Preorder traversal

C++

Python3

LeetCode 进入千题时代该如何刷题？

花花酱 LeetCode 74. Search a 2D Matrix

Solution: Binary Search

C++

花花酱 LeetCode 133. Clone Graph

Solution: Queue + Hashtable

C++

花花酱 LeetCode Weekly 123

Solutions

Huahua's Tech Road

花花酱 LeetCode 993. Cousins in Binary Tree

Solution: Preorder traversal

C++

Python3

LeetCode 进入千题时代该如何刷题？

花花酱 LeetCode 74. Search a 2D Matrix

Solution: Binary Search

C++

花花酱 LeetCode 133. Clone Graph

Solution: Queue + Hashtable

C++

花花酱 LeetCode Weekly 123

Solutions