与二叉树相关的程序题

class Solution {
public:
    void prefind(TreeNode* root, vector &ans){
        if(!root) return;
        prefind(root->left, ans);
        ans.push_back(root->val);
        prefind(root->right, ans);
    }
    
    vector inorderTraversal(TreeNode* root) {
        vector ans;
        prefind(root, ans);
        return ans;
    }
};

注：中序和后序的遍历与之类似，只是谁先谁后的顺序问题。

代码的核心，就是考虑在递归遍历的过程中，我们深度的选取是考虑左右子树中深的那颗，并在它基础上深度加1（root的深度）。

class Solution {
public:
    int prefind(TreeNode* root){
        if(!root) {
            return 0;
        }
        //返回左端最长，还是右端最长
        return max(prefind(root->left), prefind(root->right)) + 1;
    }
    
    int maxDepth(TreeNode* root) {
        int ans = prefind(root);
        return ans;
    }
};