题目汇总：https://leetcode-cn.com/tag/tree/
94. 二叉树的中序遍历中等[✔]
95. 不同的二叉搜索树 II中等（？？？）
96. 不同的二叉搜索树中等藕（？？？）
98. 验证二叉搜索树中等[✔]
99. 恢复二叉搜索树困难（？？？）
100. 相同的树简单[✔]
101. 对称二叉树简单[✔]
102. 二叉树的层序遍历中等[✔]
103. 二叉树的锯齿形层次遍历中等[✔]
104. 二叉树的最大深度简单[✔]
94. 二叉树的中序遍历中等
给定一个二叉树，返回它的中序遍历。
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
思路一：递归
首先想到的就是递归，这是最常见的解法。按照左-打印-右这种顺序遍历树就可以了，递归函数实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
List<Integer> res = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null)
return res;
helper(root,res);
return res;
}
private void helper(TreeNode root,List<Integer> res){
if(root.left != null){
inorderTraversal(root.left);
}
res.add(root.val);
if(root.right != null){
inorderTraversal(root.right);
}
}
}
思路二：迭代+栈
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了49.48%的用户
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while(root != null || stack.size() > 0){
if(root != null){
//不断往左子树方向走，每走一次就将当前节点保存到栈中，这是模拟递归的调用
stack.push(root);
root = root.left;
}else{
//当前节点为空，说明左边走到头了，从栈中弹出节点并保存，然后转向右边节点，继续上面整个过程
TreeNode temp = stack.pop();//pop()函数返回栈顶的元素，并且将该栈顶元素出栈
res.add(temp.val);
root = temp.right;
}
}
return res;
}
}
95. 不同的二叉搜索树 II中等(不会做）
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
精选题解抄的代码，正在努力看懂中......https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-7/
思路一：递归，比较好理解
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {//执行用时 :1 ms, 在所有 Java 提交中击败了99.94%的用户
List<TreeNode> ans = new ArrayList<TreeNode>();
if (n == 0) {
return ans;
}
return getAns(1, n);
}
private List<TreeNode> getAns(int start, int end) {
List<TreeNode> ans = new ArrayList<TreeNode>();
//此时没有数字，将 null 加入结果中
if (start > end) {
ans.add(null);
return ans;
}
//只有一个数字，当前数字作为一棵树加入结果中
if (start == end) {
TreeNode tree = new TreeNode(start);
ans.add(tree);
return ans;
}
//尝试每个数字作为根节点
for (int i = start; i <= end; i++) {
//得到所有可能的左子树
List<TreeNode> leftTrees = getAns(start, i - 1);
//得到所有可能的右子树
List<TreeNode> rightTrees = getAns(i + 1, end);
//左子树右子树两两组合
for (TreeNode leftTree : leftTrees) {
for (TreeNode rightTree : rightTrees) {
TreeNode root = new TreeNode(i);
root.left = leftTree;
root.right = rightTree;
//加入到最终结果中
ans.add(root);
}
}
}
return ans;
}
}
思路二：动态规划
首先我们每次新增加的数字大于之前的所有数字，所以新增加的数字出现的位置只可能是根节点或者是根节点的右孩子，右孩子的右孩子，右孩子的右孩子的右孩子等等，总之一定是右边。其次，新数字所在位置原来的子树，改为当前插入数字的左孩子即可，因为插入数字是最大的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {//执行用时 :1 ms, 在所有 Java 提交中击败了99.94%的用户
List<TreeNode> pre = new ArrayList<TreeNode>();
if (n == 0) {
return pre;
}
pre.add(null);
//每次增加一个数字
for (int i = 1; i <= n; i++) {
List<TreeNode> cur = new ArrayList<TreeNode>();
//遍历之前的所有解
for (TreeNode root : pre) {
//插入到根节点
TreeNode insert = new TreeNode(i);
insert.left = root;
cur.add(insert);
//插入到右孩子，右孩子的右孩子...最多找 n 次孩子
for (int j = 0; j <= n; j++) {
TreeNode root_copy = treeCopy(root); //复制当前的树
TreeNode right = root_copy; //找到要插入右孩子的位置
int k = 0;
//遍历 j 次找右孩子
for (; k < j; k++) {
if (right == null)
break;
right = right.right;
}
//到达 null 提前结束
if (right == null)
break;
//保存当前右孩子的位置的子树作为插入节点的左孩子
TreeNode rightTree = right.right;
insert = new TreeNode(i);
right.right = insert; //右孩子是插入的节点
insert.left = rightTree; //插入节点的左孩子更新为插入位置之前的子树
//加入结果中
cur.add(root_copy);
}
}
pre = cur;
}
return pre;
}
private TreeNode treeCopy(TreeNode root) {
if (root == null) {
return root;
}
TreeNode newRoot = new TreeNode(root.val);
newRoot.left = treeCopy(root.left);
newRoot.right = treeCopy(root.right);
return newRoot;
}
}
96. 不同的二叉搜索树中等
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
思路：动态规划
抄自题解https://leetcode-cn.com/problems/unique-binary-search-trees/solution/cdong-tai-gui-hua-zhu-bu-fen-xi-zhuang-tai-zhuan-y/
动态规划分析
在已知前n-1个数的二叉搜索树数目后，插入第n个数，有哪些情况？
1.第n个数做根节点，前n-1个数形成其左子树，右子树为0个数，dp[n-1]×dp[0]种
2.第n-1个数做根节点，左子树为前n-2个数，右子树为第n个数，dp[n-2]×dp[1]种
...
n-i+1.第i个数做根节点，左子树为前i-1个数，右子树为后n-i个数，dp[i-1]×dp[n-i]种
...
n.第1个数做根节点，左子树为0个数，右子树为后n-1个数，dp[0]×dp[n-1]种
我们将所有情况的二叉搜索树加起来即可
技巧：不妨初始化dp[0]=1,则可顺利循环解决
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
for(int i=1;i<=n;i++){// 从1...n的二叉搜索数数目
for(int j=1;j<=i;j++){// 逐步选用1...n作为根节点
dp[i] += dp[j - 1] * dp[i - j];// 左侧j-1个数，右侧i-j个数
}
}
return dp[n];
}
}
98. 验证二叉搜索树中等
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
1.节点的左子树只包含小于当前节点的数。
2.节点的右子树只包含大于当前节点的数。
3.所有左子树和右子树自身必须也是二叉搜索树。
思路一：中序遍历
一个有效的二叉搜索树中序遍历的结果一定是递增的序列，利用这个特性，对给定的二叉树中序遍历，结果记录于list之中，检验list是否为严格的升序，若是则为true，反之false。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {//执行用时 :2 ms, 在所有 Java 提交中击败了36.63%的用户
List<Integer> list = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
if(root == null)
return true;
inOrder(root);
for(int i=1;i<list.size();i++){
if(list.get(i)<=list.get(i-1)){
return false;
}
}
return true;
}
public void inOrder(TreeNode root){
if(root!=null){
inOrder(root.left);
list.add(root.val);
inOrder(root.right);
}
}
}
思路二：递归
设置上下界，依次递归比较节点值。
以下代码来自官方解题https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
public boolean isValidBST(TreeNode root) {
return helper(root, null, null);
}
public boolean helper(TreeNode node, Integer lower, Integer upper){
if(node == null){
return true;
}
//判断节点上的值是否在上下界内
int val = node.val;
if (lower != null && val <= lower)
return false;
if (upper != null && val >= upper)
return false;
//递归调用检查它的左右子树是否满足
if (! helper(node.right, val, upper))
return false;
if (! helper(node.left, lower, val))
return false;
return true;
}
}
99. 恢复二叉搜索树困难
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
进阶:
使用 O(n) 空间复杂度的解法很容易实现。
思路：递归中序遍历
/**
* 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 {
TreeNode x = null, y = null, pred = null;
public void swap(TreeNode a, TreeNode b) {//交换两个节点
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
public void findTwoSwapped(TreeNode root) {//找到两个交换节点
if (root == null) return;
findTwoSwapped(root.left);
if (pred != null && root.val < pred.val) {
y = root;
if (x == null) x = pred;
else return;
}
pred = root;
findTwoSwapped(root.right);
}
public void recoverTree(TreeNode root) {
findTwoSwapped(root);
swap(x, y);
}
}
100. 相同的树简单
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
思路：递归
dfs可以用递归来实现，dfs是一种算法，并不是具体实现，本题是用递归实现的dfs。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
if(p == null && q == null)
return true;
if(p == null || q == null)
return false;
if(p.val != q.val){
return false;
}else{
return isSameTree(p.left,q.left) && isSameTree(p.right, q.right);
}
}
}
101. 对称二叉树简单
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树[1,2,2,3,4,4,3]是对称的。但是 [1,2,2,null,3,null,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) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
return isSymmetrical(root, root);
}
boolean isSymmetrical(TreeNode root1,TreeNode root2){
if(root1 == null&&root2 == null)
return true;
if(root1 == null||root2 == null)
return false;
if(root1.val != root2.val)
return false;
return isSymmetrical(root1.left, root2.right)&&isSymmetrical(root1.right,root2.left);
}
}
102. 二叉树的层序遍历中等
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,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 {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();//单向队列
if(root != null){
queue.offer(root);//将根节点放入队列中，然后不断遍历队列
}
while(!queue.isEmpty()){
int n = queue.size();//获取当前队列的长度，也就是当前这一层的节点个数
List<Integer> level = new ArrayList<>();
for(int i = 0; i < n; i++){
TreeNode node = queue.poll();//将队列中的元素都取出来(也就是获取这一层的节点)
level.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
res.add(level);
}
return res;
}
}
103. 二叉树的锯齿形层次遍历中等
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树[3,9,20,null,null,15,7],
返回锯齿形层次遍历如下：
思路：迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了97.68%的用户
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
if(root != null){
queue.add(root);//将根节点放入队列中，然后不断遍历队列
}
int count = 0;
while(!queue.isEmpty()){
int n = queue.size();//获取当前队列的长度，也就是当前这一层的节点个数
List<Integer> level = new ArrayList<>();
for(int i=0;i<n;i++){
TreeNode node = queue.poll();
level.add(node.val);//将队列中的元素都取出来(也就是获取这一层的节点)
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
if(count % 2 == 1)//奇数层反转
Collections.reverse(level);//reverse() 用于反转指定列表中元素的顺序。
count++;
//res.add(new ArrayList<>(level));
res.add(level);
}
return res;
}
}
104. 二叉树的最大深度简单
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树[3,9,20,null,null,15,7]，
返回它的最大深度 3 。
思路：递归
如果一棵树只有一个节点，那么它的深度为1。如果根节点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1；如果根节点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1；如果既有左子树又有右子树，那么树的深度就是其左右子树深度的较大值再加1。
/**
* 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) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
if(root == null)
return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
int result = 1 + ((leftDepth > rightDepth)?leftDepth:rightDepth);
return result;
}
}
