【算法学习笔记】二叉树的最大最小高度——网上大多数的题解并不严谨？

求二叉树最大深度前序遍历用了类似回溯算法的思想当遍历到叶子节点就回溯一层。本质是求深度每往下走一层depth就1如果发现走到头了就回退一层回退的时候depth-1.void traversal(int maxd, int depth, TreeNode *cur) { if(cur-left 0 cur-right 0) { maxd max(maxd, depth); depth--; return; } if(cur-left ! 0) { traversal(maxd, depth 1, cur-left); } if(cur-right ! 0) { traversal(maxd, depth 1, cur-right); } } int maxDepth(TreeNode* root) { if(root 0) { return 0; } int maxd 0, depth 1; traversal(maxd, depth, root); return maxd; }后序遍历1.网上普遍的方法简洁但不严谨本质是求高度先从根节点走到指针为空的节点。叶子结点下一层不属于这个二叉树所以高度为0见下图这样叶子结点高度就为1了。之后return每次return就选择左右两个子树最大深度1因为return代表着返回了上一个根节点高度1.int maxHigh(TreeNode* cur) { if(cur 0) { return 0; } int leftH maxHigh(cur-left); int rightH maxHigh(cur-right); return max(leftd, rightd) 1; }如果不明白可以按照代码走一遍下面这个二叉树。如果在走的时候很困难说明递归相关知识有缺失应该先学习递归。⚠️为什么说这种方法不严谨第一种方法确定哪一次层是第0层是靠if(cur 0) return 0;“先从根节点走到指针为空的节点。叶子结点下一层不属于这个二叉树所以高度为0这样叶子结点高度就为1了”这样说没有错但是我们不能保证cur 0的空节点时叶子节点下方的空节点可能是中间某个节点的子节点。对于下图当我们走到4的右节点时cur 0我们会认为4的右子节点为空高度为零所以4的高度为1。这显然不对因为4的左边还有节点4单独一个节点这不符合二叉树高度的定义。3-2-4和7-1-2-4为这个树的两个高度这个问题对于求最大高度没有影响因为我们只会提前认为叶子节点出现这只会让我们多出一些比最大高度小的错误高度。在求最大值的max函数中就被排除了。但这会影响我们求二叉树的最小深度高度!2.严谨一些的做法只有当我们确定左右子节点全为空时我们才判断这个节点为叶子节点然后令其高度为1。为避免出现空指针的情况所以我们要就加if指针不为空的条件再进行下一次递归。int maxDepth(TreeNode* root) { if(root 0) { return 0; } if(root-left 0 root-right 0) { return 1; } int leftd 0; int rightd 0; if(root-left ! 0) { leftd maxDepth(root-left); } if(root-right ! 0) { rightd maxDepth(root-right); } return max(leftd, rightd) 1; }求二叉树最小深度前序遍历方法和求最大深度一样只需要初始化的时候把mind设置为INT_MAX然后把max函数改为min函数即可。后序遍历网上的方法也就是求最大深度的第一种方法无法直接把max改成min用来做这道题需要加很多情况讨论。第二种方法只需要把max函数改成min函数然后把leftd和rightd初值设为INT_MAX即可。这是网上方法一的分类讨论方法。class Solution { public: int getDepth(TreeNode* node) { if (node NULL) return 0; int leftDepth getDepth(node-left); int rightDepth getDepth(node-right); if (node-left NULL node-right ! NULL) { return 1 rightDepth; } if (node-left ! NULL node-right NULL) { return 1 leftDepth; } int result 1 min(leftDepth, rightDepth); return result; } int minDepth(TreeNode* root) { return getDepth(root); } };