力扣labuladong一刷day3共4题

力扣labuladong一刷day3共4题"/>

力扣labuladong一刷day3共4题

力扣labuladong一刷day3共4题

一、104. 二叉树的最大深度

题目链接：/
思路：按照拉不拉东的思路，二叉树分为两类问题，一类是遍历一边就可以解决的，另一类是通过分解问题计算答案。第一种用全局变量记录，第二章靠返回值接收子问题的答案。
想获得最大深度就是在进入一个结点之前深度加1，离开结点之后深度减1，遍历到当前节点如果是叶子节点就收集答案。

class Solution {int max = 0, deep = 0;public int maxDepth(TreeNode root) {traverse(root);return max;}void traverse(TreeNode root) {if (root == null) return;deep++;if (root.left == null && root.right == null) {max = Math.max(max, deep);}traverse(root.left);traverse(root.right);deep--;}
}

当前本题也可以采用分解子问题的思路，把求树的最大深度问题转换为求子树的最大深度问题。

class Solution {public int maxDepth(TreeNode root) {if (root == null) return 0;int left = maxDepth(root.left);int right = maxDepth(root.right);return Math.max(left, right) + 1;}
}

二、543. 二叉树的直径

题目链接：/
思路：直径指任意两个点之间的边的数量，也就是左右子树深度之和。

class Solution {int max = 0;public int diameterOfBinaryTree(TreeNode root) {traverse(root);return max;}int traverse(TreeNode root) {if (root == null) return 0;int left = traverse(root.left);int right = traverse(root.right);max = Math.max(max, left + right);return Math.max(left, right) + 1;}
}

三、144. 二叉树的前序遍历

题目链接：/
思路：前序遍历模板。

class Solution {List<Integer> list = null;public List<Integer> preorderTraversal(TreeNode root) {list = new ArrayList<>();traverse(root);return list;}void traverse(TreeNode root) {if (root == null) return;list.add(root.val);traverse(root.left);traverse(root.right);}
}

四、LCR 175. 计算二叉树的深度

题目链接：/
思路：问题不大剑指offer上的题目和力扣上一样，重复了和第一题。

class Solution {public int calculateDepth(TreeNode root) {if (root == null) return 0;int left = calculateDepth(root.left);int right = calculateDepth(root.right);return Math.max(left, right) + 1;}
}