二叉树的递归遍历

二叉树的递归遍历

递归的模板

1.确定递归函数的参数和返回值

void traversal(TreeNode* node, vector<int>& vec)

node是当前处理节点，vec用来存储结果，无返回值

2.确定终止条件

if (node == NULL) return;

递归结束的标志是当前节点为空

3.确定单层递归的逻辑

前序遍历是中左右顺序，中序遍历是左中右顺序，后序遍历是左右中顺序。根据遍历顺序，即排列下列三行代码，保存结果。

vec.push_back(node->val);
traversal(node->left);
traversal(node->right);

前序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
    void traversal(TreeNode* node, vector<int>& vec) {
        if (node == NULL) return;
        vec.push_back(node->val); //中
        traversal(node->left);    //左
        traversal(node->right);   //右
    }
}

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
    void traversal(TreeNode* node, vector<int>& vec) {
        if (node == NULL) return;
        traversal(node->left);    //左        
        vec.push_back(node->val); //中  
        traversal(node->right);   //右
    }
}     

后序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
    void traversal(TreeNode* node, vector<int>& vec) {
        if (node == NULL) return;
        traversal(node->left);    //左
        traversal(node->right);   //右
        vec.push_back(node->val); //中
    }
}

总结

• 涉及递归的都可以抽象成二叉树的问题，比如快速排序、归并排序