111. 二叉树的最小深度 - 力扣（LeetCode）

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

• 树中节点数的范围在 [0, 105] 内
• -1000 <= Node.val <= 1000

题目分析：

要求叶子节点到根节点的距离

难点在于如果根节点的左右节点中如果有一个为空，不能返回最小深度为1

则需要特殊处理左右节点中有唯一空节点的情况

思路：

使用后序遍历求的二叉树的最小高度，左右中（中用来处理数据）

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int getHeight(TreeNode* node) {if (node == NULL) return 0;int leftHeight = getHeight(node->left); //左int rightHeight = getHeight(node->right); //右//中if (node->left == NULL && node->right != NULL) {return rightHeight+1;}else if (node->left != NULL && node->right == NULL) {return leftHeight+1;}else {return min(leftHeight,rightHeight) + 1;}}int minDepth(TreeNode* root) {int result = getHeight(root);return result;}
};

if (node->left == NULL && node->right != NULL) {
            return rightHeight+1;
        }else if (node->left != NULL && node->right == NULL) {
            return leftHeight+1;
        }else {
            return min(leftHeight,rightHeight) + 1;
        }

问：这段代码中，前面两种判断不会影响到非根节点的情况吗？

答：不会的，因为我们要取得就是叶子节点，就是非空的那个节点