This is the multi-page printable view of this section. Click here to print.
树
- 1: 101. 对称二叉树
- 2: 104. 二叉树的最大深度
- 3: 543. 二叉树的直径
1 - 101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
题意:
给你一个二叉树的根节点 root ， 检查它是否轴对称。
难度:
简单
示例:
输入：root = [1,2,2,3,4,4,3] 输出：true
解析:
递归检查子树即可, 要求每一层的左右子树必须一致
先写辅助的递归, 在递归中检查左右子树是否一致, 也就是每一层左右节点是否相等
public boolean isMirror(TreeNode r1, TreeNode r2){
//第一出口, 左右节点同时为NULL
if(r1 == null && r2 == null){
return true;
}
//如果两个节点不同时为空, 代表左右两颗树层数不一致
if(r1 == null || r2 == null){
return false;
}
//递归体, 检查该层节点以及子树是否相等
return (r1.val == r2.val) &&
ismirror(r1.left, r2.right) &&
ismirror(r2.left, r1.right);
}
首先传递, 当某一层节点为NULL是回归
一旦发现左右子树不一致就返回false, 并将错误回归
当左右子树同时传递完成, 代表层数一致, 检查节点数值
之后按照对称性, 传递
-
左节点的左子树, 右节点的右子树;
-
右节点的左子树和左节点的右子树
2 - 104. 二叉树的最大深度
题意:
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
难度:
简单
示例:
解析:
此题就是经典的遍历
那么二叉树有两种遍历, BFS.DFS 我们选择DFS
DFS使用递归实现深度遍历 我们编写递归函数
public int search(TreeNode root){
//递归
//归条件
if(root == null){
return 0;
}
//递右节点
int left = search(root.left);
//递右节点
int right = search(root.right);
//归条件
return (right >= left) ? right + 1 : left + 1;
}
递归体中, 不断向下遍历子节点 第一个出口, 节点为零时回归 第二个出口, 子节点变量完成
选择左右两支中最深的返回即可