「剑指Offer」Day18：搜索与回溯算法（中等）
剑指 Offer 55 - I. 二叉树的深度
题目描述
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：给定二叉树[3,9,20,null,null,15,7]，返回它的最大深度 3 。
🔗题目链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/方法一：前序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int max;
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
getMaxDepth(root, 0);
return max;
}
public void getMaxDepth(TreeNode root, int count){
if(root == null){
return;
}
count++; //记录节点数
if(root.left == null && root.right == null){
//遍历到叶子节点就更新最大深度
max = Math.max(max, count);
return;
}
getMaxDepth(root.left, count);
getMaxDepth(root.right, count);
}
}
方法二：后序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) { //自底向上，类似于后序遍历
if(root == null){
return 0;
}
int leftDepth = maxDepth(root.left); //当前节点左子树的深度
int rightDepth = maxDepth(root.right); //右子树的深度
return Math.max(leftDepth, rightDepth) + 1; //选择左右深度中最大的进行返回，+1是为了加上当前节点
}
}
剑指 Offer 55 - II. 平衡二叉树
题目描述
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
思路
从上到下进行对各节点的左右子树进行判断，
- 构造一个获取当前节点的最大深度的函数
-
通过比较某子树的左右子树的深度差
是否成立，来判断某子树是否是平衡二叉树。
- 从根节点开始，从上到下，先判断根节点的左右子树是否平衡，平衡就接着递归判断左节点和右节点的左右子树是否平衡，以此类推，若所有子树都平衡，则此树平衡。
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
//判断当前子树是否平衡
if(Math.abs(getMaxDepth(root.left) - getMaxDepth(root.right)) <= 1){
//判断当前子树的左子树和右子树是否平衡
return isBalanced(root.left) && isBalanced(root.right);
}
return false;
}
public int getMaxDepth(TreeNode root){ //获得任意节点的左右子树的最大深度
if(root == null){
return 0;
}
return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
}
}
投递特斯拉等公司10个岗位