二叉树的最大深度，验证二叉搜索树，对称二叉树，二叉树层序遍历，将有序数组转换成二叉搜索树
二叉树的最大深度
给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度3
思路
递归计算左右子树深度
代码
/**
* 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;
} else {
int left_height = maxDepth(root.left);
int right_height = maxDepth(root.right);
return java.lang.Math.max(left_height, right_height) + 1;
}
}
}
[题目来源]https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/7/trees/47/
二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1:
输入:
2
/ \
1 3
输出: true
思路
采用中序遍历，只要满足left < root < right 即可验证
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
boolean init = false;
int small = Integer.MIN_VALUE;
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.empty()) {
while (root != null) {
stack.add(root);
root = root.left;
}
root = stack.pop();
if (init && root.val <= small) {
return false;
}
init = true;
small = root.val;
root = root.right;
}
return true;
}
}
[题目来源]https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/7/trees/48/
对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
思路
比较左右子树镜像节点是否相等
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
public boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val)
&& isMirror(t1.right, t2.left)
&& isMirror(t1.left, t2.right);
}
}
[题目来源]https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/7/trees/49/
二叉树层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）
示例：二叉树：[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
思路
递归计算每一层的节点集合
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<List<Integer>> levels = new ArrayList<List<Integer>>();
public void helper(TreeNode node, int level) {
//是否在当前层
if (levels.size() == level)
levels.add(new ArrayList<Integer>());
// 填充
levels.get(level).add(node.val);
// 遍历下一层
if (node.left != null)
helper(node.left, level + 1);
if (node.right != null)
helper(node.right, level + 1);
}
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) return levels;
helper(root, 0);
return levels;
}
}
将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
思路
中序遍历
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int[] nums;
public TreeNode helper(int left, int right) {
if (left > right) return null;
// 始终选择中间的右节点作为根节点
int p = (left + right) / 2;
if ((left + right) % 2 == 1) ++p;
// 中序遍历
TreeNode root = new TreeNode(nums[p]);
root.left = helper(left, p - 1);
root.right = helper(p + 1, right);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
this.nums = nums;
return helper(0, nums.length - 1);
}
}