[Java恶补day44] 整理模板·考点七【二叉树】

考点七【二叉树】

【考点总结】

1. 递归核心：思考整棵树与左右子树的关系，用栈保存当前是归给哪个节点 [#104]

---

104. 二叉树的最大深度

【题目】
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：
输入：root = [1,null,2]
输出：2

提示：
树中节点的数量在 [0, $10^4$] 区间内。
-100 <= Node.val <= 100

【核心思路】
方法1：

方法2：
在递归时可把节点数递下去，用全局变量维护最终答案

【复杂度】
时间复杂度：$O(n)$。n=总节点数
空间复杂度：$O(n)$。最坏情况下，退化成一条链

【代码】方法1

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}
}

【代码】方法2

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int res;public int maxDepth(TreeNode root) {dfs(root, 0);return res;}private void dfs(TreeNode root, int depth) {if (root == null)return;depth++;res = Math.max(res, depth);dfs(root.left, depth);dfs(root.right, depth);}
}

---

.

【题目】

【核心思路】

【复杂度】
时间复杂度：$O(n)$。
空间复杂度：$O()$。

【代码】

---

.

【题目】

【核心思路】

【复杂度】
时间复杂度：$O(n)$。
空间复杂度：$O()$。

【代码】

---

参考：
1、灵神视频讲解