LeetCode-num117

Populating Next Right Pointers in Each Node II
beautiful!

Problem

Follow up for problem “Populating Next Right Pointers in Each Node”.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.
For example,
Given the following binary tree,

1
2
3
4
5
    1
/ \
2 3
/ \ \
4 5 7

After calling your function, the tree should look like:

1
2
3
4
5
     1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/

class Solution
{
public:
void connect(TreeLinkNode *root)
{

queue<TreeLinkNode *> queNode;
TreeLinkNode *leftTempNode, *rightTempNode, *nowTempNode;
queue<int> queLevel;
int level = 0, nowLevel;
if (root == NULL) return;
queNode.push(root);
queLevel.push(level);
nowLevel = queLevel.front();
nowTempNode = queNode.front();
while (!queNode.empty())
{
queLevel.pop();
queNode.pop();
if (nowTempNode->left != NULL)
{
queNode.push(nowTempNode->left);
queLevel.push(nowLevel + 1);
}
if (nowTempNode->right != NULL)
{
queNode.push(nowTempNode->right);
queLevel.push(nowLevel + 1);
}
if (queNode.empty()) break;
if (nowLevel == queLevel.front())
{
nowTempNode->next = queNode.front();
}
nowTempNode = queNode.front();
nowLevel = queLevel.front();
}
}
};

Comment

  1. 上一道题代码竟然可以直接用。

LeetCode-num116

Populating Next Right Pointers in Each Node
beautiful!

Problem

Given a binary tree

1
2
3
4
5
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,

1
2
3
4
5
     1
/ \
2 3
/ \ / \
4 5 6 7

After calling your function, the tree should look like:

1
2
3
4
5
     1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/

class Solution
{
public:
void connect(TreeLinkNode *root)
{

queue<TreeLinkNode *> queNode;
TreeLinkNode *leftTempNode, *rightTempNode, *nowTempNode;
queue<int> queLevel;
int level = 0, nowLevel;
if (root == NULL) return;
queNode.push(root);
queLevel.push(level);
nowLevel = queLevel.front();
nowTempNode = queNode.front();
while (!queNode.empty())
{
queLevel.pop();
queNode.pop();
if (nowTempNode->left != NULL)
{
queNode.push(nowTempNode->left);
queLevel.push(nowLevel + 1);
}
if (nowTempNode->right != NULL)
{
queNode.push(nowTempNode->right);
queLevel.push(nowLevel + 1);
}
if (queNode.empty()) break;
if (nowLevel == queLevel.front())
{
nowTempNode->next = queNode.front();
}
nowTempNode = queNode.front();
nowLevel = queLevel.front();
}
}
};

Comment

  1. 题目做了简化;
  2. 代码是通用代码,顺便把num117AC了。

LeetCode-num098

Validate Binary Search Tree
What are you seeing?

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.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

class Solution
{
public:
bool isValidBST(TreeNode *root)
{

if (root == NULL) return true;
TreeNode *leftNode = root->left, *rightNode = root->right, *temp;
if (leftNode != NULL)
{
temp = leftNode;
while (temp->right != NULL)
{
temp = temp->right;
}
if (temp->val >= root->val) return false;
}
if (rightNode != NULL)
{
temp = rightNode;
while (temp->left != NULL)
{
temp = temp->left;
}
if (temp->val <= root->val) return false;
}
return isValidBST(leftNode) && isValidBST(rightNode);
}
};

Comment

  1. 利用递归;
  2. 值相等时处理。

LeetCode-num108

Convert Sorted Array to Binary Search Tree
sweet!

Problem

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

class Solution
{
public:
TreeNode *sortedArrayToBST(vector<int> &num)
{

if (num.empty()) return NULL;
return sortedArrayTOBSTStepByStep(num, 0, num.size() - 1);
}

TreeNode *sortedArrayTOBSTStepByStep(vector<int> &num, int begin, int end)
{

if (begin > end) return NULL;
int middle = (begin + end) / 2;
TreeNode *root = new TreeNode(num[middle]);
TreeNode *leftNode = sortedArrayTOBSTStepByStep(num, begin, middle - 1);
TreeNode *rightNode = sortedArrayTOBSTStepByStep(num, middle + 1, end);
root->left = leftNode;
root->right = rightNode;
return root;
}
};

Comment

  1. 利用递归;
  2. 开始时理解题意有错;
  3. 答案不唯一。

LeetCode-num199

Binary Tree Right Side View
coooooool!

Problem

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

1
2
3
4
5
   1            <---
/ \
2 3 <---
\ \
5 4 <---

You should return [1, 3, 4].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

class Solution
{
public:
vector<int> rightSideView(TreeNode *root)
{
vector<int> ret;
if (root == NULL) return ret;
deque<TreeNode *> deNode;
TreeNode *temp;
deque<int> deMark;
int level = 0;
deNode.push_back(root);
deMark.push_back(level);
while (!deNode.empty())
{
temp = deNode.front();
if (level == deMark.front())
{
level++;
ret.push_back(temp->val);
}
deNode.pop_front();
deMark.pop_front();
if (temp->right != NULL)
{
deNode.push_back(temp->right);
deMark.push_back(level);
}
if (temp->left != NULL)
{
deNode.push_back(temp->left);
deMark.push_back(level);
}
}
return ret;
}
};

Comment

  1. 类似层次遍历,每一层做一个标记,然后取最右边的值。

LeetCode-num103

Binary Tree Zigzag Level Order Traversal
smiling!

Problem

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

return its zigzag level order traversal as:

1
2
3
4
5
[
[3],
[20,9],
[15,7]
]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

class Solution
{
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root)
{
deque<TreeNode *> deNode;
deque<int> deD;
TreeNode *temp;
int direction;
vector<vector<int>> ret;
vector<int> tempVec;
if (root == NULL) return ret;
deNode.push_back(root);
deD.push_back(1);
while (!deNode.empty())
{
temp = deNode.front();
direction = deD.front();
tempVec.clear();
while (!deNode.empty() && direction == 1)
{
tempVec.push_back(temp->val);
deNode.pop_front();
deD.pop_front();
if (temp->left != NULL)
{
deNode.push_back(temp->left);
deD.push_back(0);
}
if (temp->right != NULL)
{
deNode.push_back(temp->right);
deD.push_back(0);
}
if (deNode.empty()) break;
temp = deNode.front();
direction = deD.front();
}
ret.push_back(tempVec);
if (deNode.empty()) break;
temp = deNode.back();
direction = deD.back();
tempVec.clear();
while (!deNode.empty() && direction == 0)
{
tempVec.push_back(temp->val);
deNode.pop_back();
deD.pop_back();
if (temp->right != NULL)
{
deNode.push_front(temp->right);
deD.push_front(1);
}
if (temp->left != NULL)
{
deNode.push_front(temp->left);
deD.push_front(1);
}
if (deNode.empty()) break;
temp = deNode.back();
direction = deD.back();
}
ret.push_back(tempVec);
}
return ret;
}
};

Comment

  1. 冗余代码太多。