文档阅读
文档阅读
二叉树解题的思维模式分两类:
1、是否可以通过遍历一遍二叉树得到答案?如果可以,用一个 traverse 函数配合外部变量来实现,这叫「遍历」的思维模式。
2、是否可以定义一个递归函数,通过子问题(子树)的答案推导出原问题的答案?如果可以,写出这个递归函数的定义,并充分利用这个函数的返回值,这叫「分解问题」的思维模式。
无论使用哪种思维模式,你都需要思考:
如果单独抽出一个二叉树节点,它需要做什么事情?需要在什么时候(前/中/后序位置)做?其他的节点不用你操心,递归函数会帮你在所有节点上执行相同的操作。
题目
104. 二叉树的最大深度
https://leetcode.cn/problems/maximum-depth-of-binary-tree/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return 1 + Math.max(left, right);
}
}
144. 二叉树的前序遍历
https://leetcode.cn/problems/binary-tree-preorder-traversal/
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
dfs(root);
return list;
}
public void dfs(TreeNode root){
if(root == null) return;
list.add(root.val);
dfs(root.left);
dfs(root.right);
}
}
543. 二叉树的直径
https://leetcode.cn/problems/diameter-of-binary-tree/
class Solution {
int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return res;
}
public int dfs(TreeNode root){
if(root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
res = Math.max(res, left + right);
return 1 + Math.max(left, right);
}
}