二叉树的几种遍历

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 941 | 阅读时间 ≈ 5

Leetcode #144 二叉树前序遍历

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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:
    void preoderTraverse(vector<int>& nums, TreeNode* node){
        nums.push_back(node -> val);
        if (node -> left) preoderTraverse(nums, node -> left);
        if (node -> right) preoderTraverse(nums, node -> right);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> nums;
        if (root == NULL) return nums;
        preoderTraverse(nums, root);
        return nums;
    }
};

Runtime: 4 ms, faster than 59.84% of C++ online submissions for Binary Tree Preorder Traversal.
Memory Usage: 9.4 MB, less than 53.45% of C++ online submissions for Binary Tree Preorder Traversal.

迭代

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

Runtime: 4 ms, faster than 59.84% of C++ online submissions for Binary Tree Preorder Traversal.
Memory Usage: 9.1 MB, less than 100.00% of C++ online submissions for Binary Tree Preorder Traversal.

Leetcode #94 二叉树中序遍历

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * 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:
    void inorderTraverse(vector<int>& nums, TreeNode* node){
        if (node -> left) inorderTraverse(nums, node -> left);
        nums.push_back(node -> val);
        if (node -> right) inorderTraverse(nums, node -> right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> nums;
        if (root == NULL) return nums;
        inorderTraverse(nums, root);
        return nums;
    }
};

Runtime: 4 ms, faster than 58.95% of C++ online submissions for Binary Tree Inorder Traversal.
Memory Usage: 9.5 MB, less than 42.00% of C++ online submissions for Binary Tree Inorder Traversal.

迭代

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
/**
 * 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> nums;
        if (root == NULL) return nums;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        while (cur || !s.empty()){
            if (cur){
                s.push(cur);
                cur = cur -> left;
            }
            else{
                cur = s.top();
                s.pop();
                nums.push_back(cur -> val);
                cur = cur -> right;
            }
        }
        return nums;
    }
};

Leetcode # 145 二叉树后序遍历

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * 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:
    void postorderTraverse(vector<int>& nums, TreeNode* node){
        if (node -> left) postorderTraverse(nums, node -> left);
        if (node -> right) postorderTraverse(nums, node -> right);
        nums.push_back(node -> val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> nums;
        if (root == NULL) return nums;
        postorderTraverse(nums, root);
        return nums;
    }
};

Runtime: 4 ms, faster than 59.20% of C++ online submissions for Binary Tree Postorder Traversal.
Memory Usage: 9.4 MB, less than 38.71% of C++ online submissions for Binary Tree Postorder Traversal.

迭代

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

/**
 * 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> postorderTraversal(TreeNode* root) {
        vector<int> nums;
        if (root == NULL) return nums;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            TreeNode* tmp = s.top();
            s.pop();
            nums.push_back(tmp -> val);
            if (tmp -> left) s.push(tmp -> left);
            if (tmp -> right) s.push(tmp -> right);
        }
        reverse(nums.begin(), nums.end());
        return nums;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Postorder Traversal.
Memory Usage: 9.1 MB, less than 93.55% of C++ online submissions for Binary Tree Postorder Traversal.

Morris遍历方法

中序

参考https://www.jianshu.com/p/484f587c967c

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
/**
 * 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:
    TreeNode* getPredecessor(TreeNode* node){
        TreeNode* p = node;
        if (p -> left){
            p = p -> left;
            while(p -> right && p -> right != node)
                p = p -> right;
        }
        return p;
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> nums;
        TreeNode* cur = root;
        while (cur){
            if (cur -> left == NULL){
                nums.push_back(cur -> val);
                cur = cur -> right;
            }
            else{
                TreeNode* pre = getPredecessor(cur);
                if (pre -> right == NULL){
                    pre -> right = cur;
                    cur = cur -> left;
                }
                else if (pre -> right == cur){
                    pre -> right = NULL;
                    nums.push_back(cur -> val);
                    cur = cur -> right;
                }
            }

        }
        return nums;
    }
};