算法搜索

树的前序、中序、后序遍历与DFS搜索

字数统计: 1.2k字   |   阅读时长: 5分
, , , ,

摘要: 树的遍历与搜索，题目清单

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

$1 前序遍历

1.1 模板题

递归前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return vector<int>();
        vector<int> result;
        _preOrder(root, result);
        return result;
    }

private:
    void _preOrder(TreeNode* root, vector<int>& result)
    {
        // 调用方保证 root 合法
        result.push_back(root -> val);

        if(root -> left)
            _preOrder(root -> left, result);
        if(root -> right)
            _preOrder(root -> right, result);
    }
};

非递归前序遍历，一次进栈

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

1.2 建树问题

1.3 编码和序列化问题

参考文章：数据压缩。

1.4 结构判断问题

1.5 N 叉树的前序遍历

$2 后序遍历

2.1 模板题

递归后续遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return vector<int>();
        vector<int> result;
        _postOrder(root, result);
        return result;
    }

private:
    void _postOrder(TreeNode* root, vector<int>& result)
    {
        // 调用方保证 root 合法
        if(root -> left)
            _postOrder(root -> left, result);
        if(root -> right)
            _postOrder(root -> right, result);

        result.push_back(root -> val);
    }
};

非递归后续遍历，两次进栈

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
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return vector<int>();
        stack<TreeNode*> output;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode *cur = st.top();
            st.pop();
            output.push(cur);
            if(cur -> left)
                st.push(cur -> left);
            if(cur -> right)
                st.push(cur -> right);
        }
        vector<int> result;
        while(!output.empty())
        {
            result.push_back(output.top() -> val);
            output.pop();
        }
        return result;
    }
};

2.2 自底向上地整合子树上的结果

2.3 N 叉树的后序遍历

$3 中序遍历

3.1 模板题

递归中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return vector<int>();
        vector<int> result;
        _inOrder(root, result);
        return result;
    }

private:
    void _inOrder(TreeNode* root, vector<int>& result)
    {
        if(root -> left)
            _inOrder(root -> left, result);
        result.push_back(root -> val);
        if(root -> right)
            _inOrder(root -> right, 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
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return vector<int>();
        vector<int> result;

        stack<TreeNode*> st;
        TreeNode *iter = root;
        while(!st.empty() || iter)
        {
            while(iter)
            {
                st.push(iter);
                iter = iter -> left;
            }
            if(!st.empty())
            {
                iter = st.top();
                st.pop();
                result.push_back(iter -> val);
                iter = iter -> right;
            }
        }
        return result;
    }
};

3.2 中序遍历的问题

中序遍历的问题主要在二叉搜索树中：

$4 树上搜索

4.1 树上非前中后序 dfs

4.2 DFS和BFS均可采用的树上搜索问题

4.3 两次遍历

以下三个题均为后序遍历接前序遍历。

4.4 数组形式的二叉树

4.5 以图的方式给出的树

4.6 DFS 遍历序

4.7 最近公共祖先

4.8 树形DP

Share