手机网站html5模板,公司网站开发背景,婚恋网站建设,wordpress文章视频文档阅读
文档阅读
二叉树解题的思维模式分两类#xff1a;
1、是否可以通过遍历一遍二叉树得到答案#xff1f;如果可以#xff0c;用一个 traverse 函数配合外部变量来实现#xff0c;这叫「遍历」的思维模式。
2、是否可以定义一个递归函数#xff0c;通过子问题
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 {ListInteger list new ArrayList();public ListInteger 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);}
}
