94. 二叉树的中序遍历

Posted on In , Views: Disqus:
LeetCode刷题系列。

描述

给定一个二叉树，返回它的中序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：94. Binary Tree Inorder Traversal

解题思路

先来一波中规中矩的递归的中序遍历，所谓中序遍历，其遍历的顺序是左子节点->根节点->右子节点，中的意思是将根节点放在中间的位置进行遍历。用递归实现的代码在大部分的基础数据结构书籍当中都会有介绍，换到本题，在具体求解时，有几个注意点：

  • 返回的指针空间初始需要分配得稍微大一点
  • * returnSize指针变量要放在辅助的遍历函数当中实时修改

具体实现代码见解法一。

除了递归，也可以借助栈用迭代来实现二叉树的中序遍历。利用栈的先进后出的特性，从根节点开始，先将根节点入栈，然后用一个循环将它的所有左子节点入栈，然后取出栈顶元素并保存到需要返回的指针变量当中，再将当前指针移动其右子节点上，若存在右子节点，则在下次循环时又可以将其所有的左子节点入栈。

这样可以保证了访问顺序是是左子节点->根节点->右子节点，具体实现代码见解法二和解法三，分别为C版本和采用STL的C版本。其中C不需要处理*returnSize变量，代码会简洁不少。

下面再介绍一种即不使用栈也不递归的二叉树遍历方法，有个专门的名字叫Morris Traversal，需要借助一种新型的数据结构，叫做Threaded binary tree，其主要步骤如下：

  • 将当前节点current初始化为根节点
  • 当当前节点不为空时，进入循环
    • 若current没有左子节点
      • 将current添加到返回结果指针
      • 将指针移动到其右子节点，即current = current->right
    • 否则，current有左子节点
      • 将 pre 指针指向 current 的左子树中的最右子节点
        • 如果pre不存在右子节点
          • 将其右子节点指回current
          • current指向其左子节点
        • 反之
          • 将pre的右子节点置空
          • 将current添加到返回结果指针
          • 将指针移动到其右子节点，即current = current->right

具体代码实现见解法四，另外，同样的Morris Traversal，在current有左子节点时的具体处理不同，还有另外一种解法，具体步骤如下：

初始二叉树状态:

1
2
3
4
5
6
7

     X
    / \
   /   \
  Y     Z
 / \   / \
A   B C   D

首先，X 是根节点，所以将 current 初始化为 X。X 有左子节点，然后将 X 放到 X 左子树的最右节点，这时 X 成为 B 的右孩子，然后将 current 设到 Y。 新的树看起来是这样的：

1
2
3
4
5
6
7
8
9
  Y
 / \
A   B
     \
      X
     / \
   (Y)  Z
       / \
      C   D

上图的(Y)代表原来的Y及其所有的孩子节点。现在树有一个链接链回原来的 X，然后遍历继续：

1
2
3
4
5
6
7
8
9
10
11
 A
  \
   Y
  / \
(A)  B
      \
       X
      / \
    (Y)  Z
        / \
       C   D

此时A已经没有左孩子节点了，然后current回到了Y，在上一步迭代当中被设置为A的右子节点。current回到了Y，这也意味着它的左子树已经遍历完毕了，然后开始输出current，从A、Y、B、X、一直到Z，这时current是Z，剩下的树，即X为根节点时的右子树，如下所示，可以以相同的模式重复以上过程。

1
2
3
4
  Z
 / \
C   D

具体代码见解法五，实现上面更为简洁。

代码

解法一

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */


// 中序遍历二叉树 
int inorder(struct TreeNode* root, int *result, int* returnSize)
{
    if(root)
    {
        // 遍历左子树
        inorder(root->left, result, returnSize);

        // 遍历根节点
        result[(*returnSize)++] = root->val;

        //遍历右子树
        inorder(root->right, result, returnSize);

    }
    return 0;
}


int* inorderTraversal(struct TreeNode* root, int* returnSize){
    
    int *result = (int *)malloc(100 * sizeof(int));
    
    *returnSize = 0;

    inorder(root, result, returnSize);

    return result;
}

解法二

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */


#define MAXSIZE 100

int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    
    int *result = (int*)malloc(sizeof(int) * MAXSIZE);
    //栈初始化
    int *stack[MAXSIZE];
    //栈顶位置标记，初始化为空
    int top = -1;
    
    struct TreeNode *p = root;
    
    *returnSize = 0;
    //树不为空或者栈不为空
    while (p != NULL || top != -1)
    {
        //当前节点及左子节点压栈
        while (p != NULL) 
        {
            stack[++top] = p;
            p = p->left;
        }
        
        //弹出栈顶元素，同时top--
        p = stack[top--];
        //将栈顶元素的值保存并将*returnSize++
        result[(*returnSize)++] = p->val;
        //将指针移动到其右子节点
        p = p->right;
    }
    return result;
}


解法三

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 a binary tree node.
 * 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> result;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (p || !s.empty()) 
        {
            while (p) 
            {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            result.push_back(p->val);
            p = p->right;
        }
        return result;
    }
};

解法四

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */


#define MAXSIZE 100

int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    
    int *result = (int*)malloc(sizeof(int) * MAXSIZE);
    
    *returnSize = 0;

    if(!root) return result;
    
    struct TreeNode *current, *pre;
    
    current = root;
    
    while(current)
    {
        if(!current->left)
        {
            result[(*returnSize)++] = current->val;
            current = current->right;
        } 
        else
        {
            pre = current->left;
            while(pre->right && pre->right != current)
                pre = pre->right;
            
            if(!pre->right)
            {
                pre->right = current;
                current = current->left;
            }
            else
            {
                pre->right = NULL;
                result[(*returnSize)++] = current->val;
                current = current->right;
            }
            
        }
    }
    return result;
}

解法五

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 a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */


#define MAXSIZE 100

int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    
    int *result = (int*)malloc(sizeof(int) * MAXSIZE);
    
    *returnSize = 0;

    if(!root) return result;
    
    struct TreeNode *current, *pre, *tmp;
    
    current = root;
    
    while(current)
    {
        if(!current->left)
        {
            result[(*returnSize)++] = current->val;
            current = current->right;
        } 
        else
        {
            pre = current->left;
            while(pre->right)
                pre = pre->right;
            
            pre->right = current;
            tmp = current;
            current = current->left;
            tmp->left = NULL;
            
        }
    }
    return result;
}

参考