五月集训（第十九日）二叉树

• 一、144. 二叉树的前序遍历
• • 1.原题链接
  • 2.题目描述
  • 3.解题思路
  • 4.源码
• 二、94. 二叉树的中序遍历
• • 1.原题链接
  • 2.题目描述
  • 3.解题思路
  • 4.源码
• 三、145. 二叉树的后序遍历
• • 1.原题链接
  • 2.题目描述
  • 3.解题思路
  • 4.源码
• 四、104. 二叉树的最大深度
• • 1.原题链接
  • 2.题目描述
  • 3.解题思路
  • 4.源码
• 总结

144. 二叉树的前序遍历

        给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

        dfs即可

class Solution {
public:
    vector ret;

    void dfs(TreeNode* root){
        if(root){
        ret.push_back(root->val);
        dfs(root->left);
        dfs(root->right);
        }
        
    }
    vector preorderTraversal(TreeNode* root) {
        ret.clear();
        dfs(root);
        return ret;
    }
};

94. 二叉树的中序遍历

        给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

        同上题

class Solution {
public:
    vector ret;

    void dfs(TreeNode* root){
        if(root){
        dfs(root->left);
        ret.push_back(root->val);
        dfs(root->right);
        }
        
    }
    vector inorderTraversal(TreeNode* root) {
        ret.clear();
        dfs(root);
        return ret;
    }
};

145. 二叉树的后序遍历

        给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

        同上题

class Solution {
public:
    vector ret;

    void dfs(TreeNode* root){
        if(root){
        dfs(root->left);
        dfs(root->right);
        ret.push_back(root->val);     
        }
        
    }
    vector postorderTraversal(TreeNode* root) {
        ret.clear();
        dfs(root);
        return ret;
    }
};

104. 二叉树的最大深度

        给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

        深度优先搜索

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==nullptr){
            return 0;
        }
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

        第十九天，今天比较水，还需加油。