题解 | 牛群的最大高度

语言： C++

知识点： 二叉树的遍历

分析： 本题要求二叉树中最大的节点值，因此遍历整颗二叉树，依次比较各个节点值记录其中较大的值，最终遍历完成后即可得到最大节点值。下面分别给出前序遍历、中序遍历、后序遍历二叉树的递归和迭代共六种代码实现方法：

代码实现：

方法一：前序遍历

递归：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int maxN = 0;
    void preTravel(TreeNode* node)
    {
        if(node == nullptr)
        {
            return ;
        }
        if(node->val > maxN) // 根
        {
            maxN = node->val;
        }
        preTravel(node->left); // 左
        preTravel(node->right); // 右
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int findMaxHeight(TreeNode* root) {
        preTravel(root);
        return maxN;
    }
};

迭代： 使用栈存放节点辅助遍历，注意左右子节点的入栈顺序，左节点后入栈才能实现先访问左节点，才符合前序遍历顺序。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int findMaxHeight(TreeNode* root) {
        int maxN = 0;
        stack<TreeNode*> sk;
        sk.push(root); // 此处题目根节点一定非空因此直接入栈，其他情况应注意判空
        while(!sk.empty())
        {
            TreeNode* node = sk.top(); // 根
            sk.pop();
            if(node->val > maxN)
            {
                maxN = node->val;
            }
            if(node->right) // 右（注意此处入栈的顺序，栈先入后出因此先入右节点）
            {
                sk.push(node->right);
            }
            if(node->left) // 左
            {
                sk.push(node->left);
            }
        }
        return maxN;
    }
};

方法二：中序遍历

递归：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int maxN = 0;
    void inTravel(TreeNode* node)
    {
        if(node == nullptr)
        {
            return ;
        }
        inTravel(node->left); // 左
        if(node->val > maxN) // 根
        {
            maxN = node->val;
        }
        inTravel(node->right); // 右
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int findMaxHeight(TreeNode* root) {
        inTravel(root);
        return maxN;
    }
};

迭代： 中序遍历时需额外使用一个指针辅助遍历。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int findMaxHeight(TreeNode* root) {
        int maxN = 0;
        stack<TreeNode*> sk;
        TreeNode* node = root;
        while(node != nullptr || !sk.empty())
        {
            if(node != nullptr)
            {
                sk.push(node);
                node = node->left; // 左
            }
            else
            {
                node = sk.top(); // 根
                sk.pop();
                if(node->val > maxN)
                {
                    maxN = node->val;
                }
                node = node->right; // 右
            }
        }
        return maxN;
    }
};

方法三：后序遍历

递归：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int maxN = 0;
    void postTravel(TreeNode* node)
    {
        if(node == nullptr)
        {
            return ;
        }
        postTravel(node->left); // 左
        postTravel(node->right); // 右
        if(node->val > maxN) // 根
        {
            maxN = node->val;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int findMaxHeight(TreeNode* root) {
        postTravel(root);
        return maxN;
    }
};

迭代： 后序遍历的顺序为左右根，而前序遍历顺序为根左右，因此可以在前序迭代遍历时，将左右子节点入栈顺序交换变为根右左，之后再使用reverse翻转一下最终结果即可得到左右根的遍历顺序（即后序遍历）。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int findMaxHeight(TreeNode* root) {
        int maxN = 0;
        stack<TreeNode*> sk;
        sk.push(root);
        while(!sk.empty())
        {
            TreeNode* node = sk.top(); // 根
            sk.pop();
            if(node->val > maxN)
            {
                maxN = node->val;
            }
            if(node->left) // 此处先入栈左节点，使最终遍历顺序为根右左（栈先入后出）
            {
                sk.push(node->left);
            }
            if(node->right) // 右
            {
                sk.push(node->right);
            }
        }
        // 假设遍历过程中的节点值存储在vector<int> res中，此处将其翻转即可得到左右根即后序遍历的顺序。（本题只需找最大值，因此不需要存储节点值，所以此处不用写）
        //reverse(res.begin(), res.end());
        return maxN;
    }
};