二叉树的几种遍历

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 == NULLreturn 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 == NULLreturn 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 == NULLreturn 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;
}
};