树的深度优先、广度优先easy题
树的深度优先、广度优先easy题
习题来自于leetCode深度优先课程后续练习推荐习题。【https://leetcode-cn.com/leetbook/read/dfs/euapvg/】
一、104.二叉树的最大深度
1.1、题目
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
1.2、题解思路与算法
题解思路于算法很简单，只需要简单的深度优先获取所有的叶子节点到根节点的长度，然后取出最大值即可。具体查看实现。
1.3、题解代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
}
}
二、111.二叉树的最小深度
2.1、题目
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 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
2.2、题解思路与算法
题解思路与104相同，只不过将最深换成最浅的思想，需要注意的是，如果节点一册为空则不会计算到所属分支中。具体查看代码实现。
2.3、题解代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null) {
return 0;
}
if(root.left == null) {
return minDepth(root.right) + 1;
}
if(root.right == null) {
return minDepth(root.left) + 1;
}
return Math.min(minDepth(root.left) + 1, minDepth(root.right) + 1);
}
}
三、112.路径总和
3.1、题目
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22输出：true示例 2：
输入：root = [1,2,3], targetSum = 5输出：false示例 3：
输入：root = [1,2], targetSum = 0输出：false
提示：
树中节点的数目在范围 [0, 5000] 内-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
3.2、题解思路与算法
采用树的深度遍历中的前序遍历， 由此可知每个叶子节点到根节点的长度满足题目的targetSum则为true，反之为false，具体查看代码实现。
3.3、题解代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) {
return false;
}
// 减去当前路径的所对应的值
targetSum -= root.val;
// 判断值为0并且为叶子节点，则为true
if(targetSum == 0 && root.left == null && root.right == null) {
return true;
}
// 有一条分支满足即可
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
}
}
四、226.翻转二叉树
4.1、题目
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
4.2、题解思路与算法
本题目我是用的是广度优先，一层一层调换左右节点位置。也可以用深度优先（后序遍历）。具体查看代码实现。
4.3、题解代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return root;
}
Deque<TreeNode> deque = new ArrayDeque<>(Arrays.asList(root));
while( !deque.isEmpty() ) {
TreeNode curNode = deque.pollFirst();
TreeNode left = curNode.left;
TreeNode right = curNode.right;
// invert this level
curNode.right = left;
curNode.left = right;
// insert deque
if(left != null) deque.addLast(left);
if(right != null) deque.addLast(right);
}
return root;
}
}
题目取自leetcode官网。