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. 冗余代码太多。

LeetCode-num106

Construct Binary Tree from Inorder and Postorder Traversal
programmer

Problem

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution

1
/**
 * 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 *buildTree(vector<int> &inorder, vector<int> &postorder)
	{
		if (postorder.size() != inorder.size()) return NULL;
		else if (postorder.empty()) return NULL;
		return buildTreeStepByStep(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
	}

	TreeNode *buildTreeStepByStep(vector<int> &inorder, int inBegin, int inEnd, vector<int> &postorder, int posBegin, int posEnd)
	{
		if (inBegin == inEnd || posBegin == posEnd) return new TreeNode(postorder[posEnd]);
		int rootNum = postorder[posEnd];
		int position = findPosition(inorder, inBegin, inEnd, rootNum);
		int leftLen = position - inBegin;
		TreeNode *root = new TreeNode(rootNum), *leftNode, *rightNode;
		if (position != inBegin)
		{
			leftNode = buildTreeStepByStep(inorder, inBegin, position - 1, postorder, posBegin, posBegin + leftLen - 1);
			root->left = leftNode;
		}
		if (position != inEnd)
		{
			rightNode = buildTreeStepByStep(inorder, position + 1, inEnd, postorder, posBegin + leftLen, posEnd - 1);
			root->right = rightNode;
		}
		return root;
	}

	int findPosition(vector<int> vec, int begin, int end, int num)
	{
		for (int i = begin; i <= end; i++)
		{
			if (vec[i] == num) return i;
		}
		return -1;
	}
};

Comment

  1. 与上一道题类似。

LeetCode-num105

Construct Binary Tree from Preorder and Inorder Traversal
doubi!

Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

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
/**
* 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 *buildTree(vector<int> &preorder, vector<int> &inorder)
{

if (preorder.size() != inorder.size()) return NULL;
else if (preorder.empty()) return NULL;
return buildTreeStepByStep(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}

TreeNode *buildTreeStepByStep(vector<int> &preorder, int preBegin, int preEnd, vector<int> &inorder, int inBegin, int inEnd)
{

if (preBegin == preEnd || inBegin == inEnd) return new TreeNode(preorder[preBegin]);
int rootNum = preorder[preBegin];
int position = findPosition(inorder, inBegin, inEnd, rootNum);
int leftLen = position - inBegin;
TreeNode *root = new TreeNode(rootNum), *leftNode, *rightNode;
if (position != inBegin)
{
leftNode = buildTreeStepByStep(preorder, preBegin + 1, preBegin + leftLen, inorder, inBegin, position - 1);
root->left = leftNode;
}
if (position != inEnd)
{
rightNode = buildTreeStepByStep(preorder, preBegin + leftLen + 1, preEnd, inorder, position + 1, inEnd);
root->right = rightNode;
}
return root;
}

int findPosition(vector<int> vec, int begin, int end, int num)
{

for (int i = begin; i <= end; i++)
{
if (vec[i] == num) return i;
}
return -1;
}
};

Comment

  1. 不改变原向量结构,利用递归实现。

LeetCode-num094

Binary Tree Inorder Traversal
Inorder Traversal

Problem

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
1
\
2
/
3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

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
/**
* 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> inorderTraversal(TreeNode *root)
{
vector<int> ret;
TreeNode *temp = root;
stack<TreeNode *> treeSta;
if (root == NULL) return ret;
treeSta.push(root);
while (temp->left != NULL)
{
temp = temp->left;
treeSta.push(temp);
}
while (!treeSta.empty())
{
temp = treeSta.top();
treeSta.pop();
ret.push_back(temp->val);
if (temp->right != NULL)
{
temp = temp->right;
treeSta.push(temp);
while (temp->left != NULL)
{
temp = temp->left;
treeSta.push(temp);
}
}
}
return ret;
}
};

Comment

  1. 递归实现较简单,题中要求迭代完成,实现难度增大。

LeetCode-num145

Binary Tree Postorder Traversal
yeah!

Problem

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
1
\
2
/
3

return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

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
/**
* 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> postorderTraversal(TreeNode *root)
{
vector<int> ret, leftRet, rightRet;
TreeNode *temp = root;
if (root == NULL) return ret;
stack<TreeNode *> nodeSta, tempSta;
while (temp != NULL)
{
nodeSta.push(temp);
temp = temp->left;
}
while (!nodeSta.empty())
{
temp = nodeSta.top();
if (temp->right == NULL)
{
ret.push_back(temp->val);
nodeSta.pop();
}
else
{
if (!tempSta.empty() && temp == tempSta.top())
{
tempSta.pop();
ret.push_back(temp->val);
nodeSta.pop();
continue;
}
tempSta.push(temp);
temp = temp->right;
while (temp != NULL)
{
nodeSta.push(temp);
temp = temp->left;
}
}
}
return ret;
}
};

递归解法:

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
/**
* 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> postorderTraversal(TreeNode *root)
{
vector<int> ret, leftRet, rightRet;
TreeNode *temp = root;
if (root == NULL) return ret;
leftRet = postorderTraversal(root->left);
rightRet = postorderTraversal(root->right);
ret.assign(leftRet.begin(), leftRet.end());
ret.insert(ret.end(), rightRet.begin(), rightRet.end());
ret.push_back(root->val);
return ret;
}
};

Comment

  1. 后续遍历的迭代做法难度较大;
  2. 利用两个栈。