题目链接：Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
confused what “{1,#,2,3}” means?
read more on how binary tree is serialized on OJ.
OJ’s Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.
这道题的要求是中序遍历二叉树。
二叉树，即每个节点下面最多有2个子节点的树。
-
递归遍历
递归遍历二叉树，比较简单。
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
public:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> vi;
inorderTraversal(root, vi);
return vi;
}
private:
void inorderTraversal(TreeNode *root, vector<int> &vi)
{
if(root != NULL)
{
inorderTraversal(root -> left, vi);
vi.push_back(root -> val);
inorderTraversal(root -> right, vi);
}
}
};
-
迭代遍历1
用栈进行存储，根节点先入栈。然后不断读取栈顶元素，读取某一节点的时候，如果存在左子树，说明需要先遍历左子树，因此该节点不出栈，左子树入栈，并标记左子树为NULL。如果不存在左子树，出栈，并记录该节点。如果该节点存在右子树，右子数入栈。
该方法缺点，破坏了原二叉树的结构。
时间复杂度：O(n)
空间复杂度：O(n)
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
class Solution
{
public:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> vi;
if(root == NULL)
return vi;
stack<TreeNode *> stp;
stp.push(root);
while(!stp.empty())
{
TreeNode *p = stp.top();
if(p -> left != NULL)
{
stp.push(p -> left);
p -> left = NULL;
}
else
{
stp.pop();
vi.push_back(p -> val);
if(p -> right != NULL)
stp.push(p -> right);
}
}
return vi;
}
};
-
迭代遍历2
由于上面思路破坏了原二叉树的结构，因此不常被采用。下面这段代码用栈实现遍历二叉树，并不破坏原有二叉树结构。
时间复杂度：O(n)
空间复杂度：O(n)
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
class Solution
{
public:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> vi;
stack<TreeNode *> stp;
TreeNode *cur = root;
while(cur != NULL || !stp.empty())
{
while(cur != NULL)
{
stp.push(cur);
cur = cur -> left;
}
cur = stp.top();
stp.pop();
vi.push_back(cur -> val);
cur = cur -> right;
}
return vi;
}
};
-
Morris Traversal方法
该方法只需要O(1)空间，而且同样可以在O(n)时间内完成遍历二叉树。
- 如果当前节点（cur）的左子树为空（cur->left==NULL），则输出当前节点（cur->val）并将其右子树作为当前节点（cur=cur->right）。
- 如果当前节点的左子树不为空（cur->left!=NULL），在当前节点的左子树中找到当前节点在中序遍历下的前驱节点（pre）。(1)如果前驱节点的右子树为空（pre->right==NULL），将它的右子树设置为当前节点（pre->right=cur）。当前节点更新为当前节点的左子树（cur=cur->left）。(2)如果前驱节点的右子树为当前节点（pre->right==cur），将它的右子树重新设为空（pre->right=NULL，恢复树的形状）。输出当前节点（cur->val）。当前节点更新为当前节点的右子树（cur=cur->right）。
- 重复以上1、2直到当前节点为空。
时间复杂度：O(n)
空间复杂度：O(n)
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
class Solution
{
public:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> vi;
TreeNode *cur = root, *pre = NULL;
while(cur != NULL)
{
if(cur -> left == NULL)
{
vi.push_back(cur -> val);
cur = cur -> right;
}
else
{
pre = cur -> left;
while(pre -> right != NULL && pre -> right != cur)
pre = pre -> right;
if(pre -> right == NULL)
{
pre -> right = cur;
cur = cur -> left;
}
else
{
pre -> right = NULL;
vi.push_back(cur -> val);
cur = cur -> right;
}
}
}
return vi;
}
};
详见这里。