二叉树（纲领篇）

文档阅读

文档阅读

二叉树解题的思维模式分两类：

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);}
}