// 记录最大深度
int res = 0;
int depth = 0;
// 主函数
intmaxDepth(TreeNode root) {
traverse(root);
return res;
}
// 二叉树遍历框架
voidtraverse(TreeNode root) {
if (root ==null) {
// 到达叶子节点
res = Math.max(res, depth);
return;
}
// 前序遍历位置
depth++;
traverse(root.left);
traverse(root.right);
// 后序遍历位置
depth--;
}
// 记录所有全排列
List<List<Integer>> res =new LinkedList<>();
LinkedList<Integer> track =new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
backtrack(nums);
return res;
}
// 回溯算法框架
voidbacktrack(int[] nums) {
if (track.size() == nums.length) {
// 穷举完一个全排列
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
if (track.contains(nums[i]))
continue;
// 前序遍历位置做选择
track.add(nums[i]);
backtrack(nums);
// 后序遍历位置取消选择
track.removeLast();
}
}
// 定义：输入根节点，返回这棵二叉树的最大深度
intmaxDepth(TreeNode root) {
if (root ==null) {
return 0;
}
// 递归计算左右子树的最大深度
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 整棵树的最大深度
int res = Math.max(leftMax, rightMax) + 1;
return res;
}
// 定义：输入金额 amount，返回凑出 amount 的最少硬币个数
intcoinChange(int[] coins,int amount) {
// base case
if (amount == 0)return 0;
if (amount < 0)return -1;
int res = Integer.MAX_VALUE;
for (int coin : coins) {
// 递归计算凑出 amount - coin 的最少硬币个数
int subProblem = coinChange(coins, amount - coin);
if (subProblem == -1)continue;
// 凑出 amount 的最少硬币个数
res = Math.min(res, subProblem + 1);
}
return res == Integer.MAX_VALUE ? -1 : res;
}
// 输入一棵二叉树的根节点，层序遍历这棵二叉树
voidlevelTraverse(TreeNode root) {
if (root ==null)return 0;
Queue<TreeNode> q =new LinkedList<>();
q.offer(root);
int depth = 1;
// 从上到下遍历二叉树的每一层
while (!q.isEmpty()) {
int sz = q.size();
// 从左到右遍历每一层的每个节点
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
if (cur.left !=null) {
q.offer(cur.left);
}
if (cur.right !=null) {
q.offer(cur.right);
}
}
depth++;
}
}
评论区