用家用光纤宽带做网站,企业黄页电话,wordpress分类编辑器,深圳专业营销网站公司代码随想录-二叉树 | 111 二叉树的最小深度 LeetCode 111 二叉树的最小深度解题思路代码难点总结 LeetCode 111 二叉树的最小深度
题目链接 代码随想录
题目描述
给定一个二叉树#xff0c;找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说… 代码随想录-二叉树 | 111 二叉树的最小深度 LeetCode 111 二叉树的最小深度解题思路代码难点总结 LeetCode 111 二叉树的最小深度
题目链接 代码随想录
题目描述
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明叶子节点是指没有子节点的节点。
解题思路
判断 递归法 确定递归函数的参数和返回值参数-根节点返回值-最小深度确定终止条件节点为空返回0表示当前高度为0确定单层递归的逻辑判断是否为叶子节点若不是 左子树为空最小深度 1 右子树最小深度右子树为空最小深度 1 左子树最小深度。 迭代法层序遍历 终止条件当左右孩子都为空时说明遍历到了最低点。
代码
递归法
class Solution {public int minDepth(TreeNode root) {if(root null) return 0;int leftDepth minDepth(root.left);int rightDepth minDepth(root.right);if(root.left null) return rightDepth 1;if(root.right null) return leftDepth 1;//左右节点都不为nullreturn Math.min(leftDepth, rightDepth) 1;}
}迭代法
class Solution {public int minDepth(TreeNode root) {if(root null) return 0;DequeTreeNode deque new LinkedList();deque.offer(root);int depth 0;while(!deque.isEmpty()){depth;int size deque.size();for(int i 0; i size; i){TreeNode node deque.poll();if(node.left null node.right null) return depth;if(node.left ! null) deque.offer(node.left);if(node.right ! null) deque.offer(node.right);}}return depth;}
}难点
递归法中单层递归的逻辑
总结
巩固了递归法和迭代法。
