二叉树相关题目刷题心得
import java.util.*;
public class Solution {
public int lowestCommonAncestor (TreeNode root, int p, int q) {
//空树找不到公共祖先
if(root == null)
return -1;
//pq在该节点两边说明这就是最近公共祖先
if((p >= root.val && q <= root.val) || (p <= root.val && q >= root.val))
return root.val;
//pq都在该节点的左边
else if(p <= root.val && q <= root.val)
//进入左子树
return lowestCommonAncestor(root.left, p, q);
//pq都在该节点的右边
else
//进入右子树
return lowestCommonAncestor(root.right, p, q);
}
}
前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
数据范围：二叉树的节点数量满足 0 \le n \le 100 \0≤n≤100 ，二叉树节点的值满足 1 \le val \le 100 \1≤val≤100 ，树的各节点的值各不相同 示例 1：
示例 1：
思路：
什么是二叉树的前序遍历？简单来说就是“根左右”，展开来说就是对于一颗二叉树优先访问其根节点，然后访问它的左子树，等左子树全部访问完了再访问其右子树，而对于子树也按照之前的访问方式，直到到达叶子节点。
从上述前序遍历的解释中我们不难发现，它存在递归的子问题：每次访问一个节点之后，它的左子树是一个要前序遍历的子问题，它的右子树同样是一个要前序遍历的子问题。那我们可以用递归处理：
- 终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
- 返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
- 本级任务： 每个子问题优先访问这棵子树的根节点，然后递归进入左子树和右子树。
具体做法：
- step 1：准备数组用来记录遍历到的节点值，Java可以用List，C++可以直接用vector。
- step 2：从根节点开始进入递归，遇到空节点就返回，否则将该节点值加入数组。
- step 3：依次进入左右子树进行递归。
Java实现代码： import java.util.*;
public class Solution {
public void preorder(List<Integer> list, TreeNode root){
//遇到空节点则返回
if(root == null)
return;
//先遍历根节点
list.add(root.val);
//再去左子树
preorder(list, root.left);
//最后去右子树
preorder(list, root.right);
}
public int[] preorderTraversal (TreeNode root) {
//添加遍历结果的数组
List<Integer> list = new ArrayList();
//递归前序遍历
preorder(list, root);
//返回的结果
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++)
res[i] = list.get(i);
return res;
}
}
中序遍历
给定一个二叉树的根节点root，返回它的中序遍历结果。
数据范围：树上节点数满足 0 \le n \le 10000≤n≤1000，树上每个节点的值满足 0 \le val \le 10000≤val≤1000
进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
示例1
输入： {1,2,#,#,3} 返回值： [2,3,1]
什么是二叉树的中序遍历，简单来说就是“左根右”，展开来说就是对于一棵二叉树，我们优先访问它的左子树，等到左子树全部节点都访问完毕，再访问根节点，最后访问右子树。同时访问子树的时候，顺序也与访问整棵树相同。
从上述对于中序遍历的解释中，我们不难发现它存在递归的子问题，根节点的左右子树访问方式与原本的树相同，可以看成一颗树进行中序遍历，因此可以用递归处理：
- 终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
- 返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
- 本级任务： 每个子问题优先访问左子树的子问题，等到左子树的结果返回后，再访问自己的根节点，然后进入右子树。
具体做法：
- step 1：准备数组用来记录遍历到的节点值，Java可以用List，C++可以直接用vector。
- step 2：从根节点开始进入递归，遇到空节点就返回，否则优先进入左子树进行递归访问。
- step 3：左子树访问完毕再回到根节点访问。
- step 4：最后进入根节点的右子树进行递归。
Java实现代码： import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型一维数组
*/
public void preorder(List<Integer> list, TreeNode root){
//遇到空节点则返回
if(root == null)
return;
//去左子树
preorder(list, root.left);
//遍历根节点
list.add(root.val);
//最后去右子树
preorder(list, root.right);
}
public int[] inorderTraversal (TreeNode root) {
// write code here
List<Integer> list = new ArrayList();
//递归前序遍历
preorder(list, root);
//返回的结果
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++)
res[i] = list.get(i);
return res;
}
} 后序遍历同理
求二叉树的层序遍历
1.队列法
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
// 队列保存每一层所有结点
Queue<TreeNode> queue = new LinkedList<>();
// 先放入根节点
queue.offer(root);
while(!queue.isEmpty()) {
// 收集当前层的所有结点的值
ArrayList<Integer> list = new ArrayList<>();
// ·当前层的节点数量
int count = queue.size();
// 遍历每一层
while(count-- > 0) {
// 从对头取出节点
TreeNode node = queue.poll();
// 收集结果
list.add(node.val);
// 左右节点按顺序加到队尾
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
res.add(list);
}
return res;
}
} 2.递归法 import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
DFS(root,res,0);
return res;
}
public void DFS(TreeNode root, ArrayList<ArrayList<Integer>> list, int depth){
// 递归终止条件
if(root == null) {
return;
}
// 初始化集合，该集合用来保存层数为depth时的结点值，depth相当于结果集合list的索引
if(list.size() == depth) {
list.add(new ArrayList<>());
}
// dfs，递归直到叶子节点
DFS(root.left, list, depth + 1);
// 收集层数为depth的结果集
list.get(depth).add(root.val);
DFS(root.right, list, depth + 1);
}
} 按之字形顺序打印二叉树
描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
数据范围：0 \le n \le 15000≤n≤1500,树上每个节点的val满足 |val| <= 1500∣val∣<=1500
要求：空间复杂度：O(n)O(n)，时间复杂度：O(n)O(n) 例如：
给定的二叉树是{1,2,3,#,#,4,5}
方法：双栈
图解
算法流程：
- 维护两个栈，一个存放奇数层的节点，一个存放偶数层的节点
- 整型变量level表示当前遍历第几层，奇数则顺序打印，偶数逆序打印, 从第1层开始
- 分奇数层和偶数层处理
- 奇数层按顺序，每次偶数层的栈保存偶数层节点，先存左结点，这样等下次pop时就是右节点先打印
- 偶数层反序，每次奇数层的栈保存偶数层节点，先存右结点，这样等下次pop时就是左节点先打印
代码如下：
import java.util.*;
import java.util.ArrayList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(pRoot == null) {
return res;
}
// 存放奇数层的节点
Stack<TreeNode> stack1 = new Stack<>();
stack1.push(pRoot);
// 存放偶数层的节点
Stack<TreeNode> stack2 = new Stack<>();
int level = 1;
while(!stack1.isEmpty() || !stack2.isEmpty()) {
if(level % 2 != 0) {
ArrayList<Integer> list = new ArrayList<>();
// 奇数层按顺序
while(!stack1.isEmpty()) {
TreeNode node = stack1.pop();
if(node != null) {
// 收集打印结果
list.add(node.val);
// stack2保存偶数层节点，先存左结点，这样等下次pop时就是右节点先打印，满足题目要求
stack2.push(node.left);
stack2.push(node.right);
}
}
// 收集当前层的结果
if(!list.isEmpty()) {
res.add(list);
level++;
}
} else {
// 处理偶数层
ArrayList<Integer> list = new ArrayList<>();
while(!stack2.isEmpty()) {
TreeNode node = stack2.pop();
if(node != null) {
list.add(node.val);
// 需要按顺序push，因为stack1是用在奇数层按顺序输出结果的
stack1.add(node.right);
stack1.add(node.left);
}
}
if(!list.isEmpty()) {
res.add(list);
level++;
}
}
}
return res;
}
}
二叉树的最大深度
描述
求给定二叉树的最大深度， 深度是指树的根节点到任一叶子节点路径上节点的数量。 最大深度是所有叶子节点的深度的最大值。 （注：叶子节点是指没有子节点的节点。）
算法流程：
- 定义递归函数功能：获取root结点的最大深度
- 递归终止条件：root为null
- 返回值：先递归左子结点，再递归右子结点，最后求出每一子树的深度的最大值
代码如下：
public int maxDepth (TreeNode root) {
// write code
if(root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
二叉树中和为某一值的路径(一)
描述
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数目为n
例如：
给出如下的二叉树，\ sum=22 sum=22，
返回true，因为存在一条路径 5\to 4\to 11\to 25→4→11→2的节点值之和为 22
import java.util.*;
public class Solution {
public void preorder(List<Integer> list, TreeNode root){
//遇到空节点则返回
if(root == null)
return;
//先遍历根节点
list.add(root.val);
//再去左子树
preorder(list, root.left);
//最后去右子树
preorder(list, root.right);
}
public int[] preorderTraversal (TreeNode root) {
//添加遍历结果的数组
List<Integer> list = new ArrayList();
//递归前序遍历
preorder(list, root);
//返回的结果
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++)
res[i] = list.get(i);
return res;
}
}
中序遍历
给定一个二叉树的根节点root，返回它的中序遍历结果。
数据范围：树上节点数满足 0 \le n \le 10000≤n≤1000，树上每个节点的值满足 0 \le val \le 10000≤val≤1000
进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
示例1
输入： {1,2,#,#,3} 返回值： [2,3,1]
什么是二叉树的中序遍历，简单来说就是“左根右”，展开来说就是对于一棵二叉树，我们优先访问它的左子树，等到左子树全部节点都访问完毕，再访问根节点，最后访问右子树。同时访问子树的时候，顺序也与访问整棵树相同。
从上述对于中序遍历的解释中，我们不难发现它存在递归的子问题，根节点的左右子树访问方式与原本的树相同，可以看成一颗树进行中序遍历，因此可以用递归处理：
- 终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
- 返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
- 本级任务： 每个子问题优先访问左子树的子问题，等到左子树的结果返回后，再访问自己的根节点，然后进入右子树。
具体做法：
- step 1：准备数组用来记录遍历到的节点值，Java可以用List，C++可以直接用vector。
- step 2：从根节点开始进入递归，遇到空节点就返回，否则优先进入左子树进行递归访问。
- step 3：左子树访问完毕再回到根节点访问。
- step 4：最后进入根节点的右子树进行递归。
Java实现代码： import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型一维数组
*/
public void preorder(List<Integer> list, TreeNode root){
//遇到空节点则返回
if(root == null)
return;
//去左子树
preorder(list, root.left);
//遍历根节点
list.add(root.val);
//最后去右子树
preorder(list, root.right);
}
public int[] inorderTraversal (TreeNode root) {
// write code here
List<Integer> list = new ArrayList();
//递归前序遍历
preorder(list, root);
//返回的结果
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++)
res[i] = list.get(i);
return res;
}
} 后序遍历同理
求二叉树的层序遍历
1.队列法
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
// 队列保存每一层所有结点
Queue<TreeNode> queue = new LinkedList<>();
// 先放入根节点
queue.offer(root);
while(!queue.isEmpty()) {
// 收集当前层的所有结点的值
ArrayList<Integer> list = new ArrayList<>();
// ·当前层的节点数量
int count = queue.size();
// 遍历每一层
while(count-- > 0) {
// 从对头取出节点
TreeNode node = queue.poll();
// 收集结果
list.add(node.val);
// 左右节点按顺序加到队尾
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
res.add(list);
}
return res;
}
} 2.递归法 import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
DFS(root,res,0);
return res;
}
public void DFS(TreeNode root, ArrayList<ArrayList<Integer>> list, int depth){
// 递归终止条件
if(root == null) {
return;
}
// 初始化集合，该集合用来保存层数为depth时的结点值，depth相当于结果集合list的索引
if(list.size() == depth) {
list.add(new ArrayList<>());
}
// dfs，递归直到叶子节点
DFS(root.left, list, depth + 1);
// 收集层数为depth的结果集
list.get(depth).add(root.val);
DFS(root.right, list, depth + 1);
}
} 按之字形顺序打印二叉树
描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
数据范围：0 \le n \le 15000≤n≤1500,树上每个节点的val满足 |val| <= 1500∣val∣<=1500
要求：空间复杂度：O(n)O(n)，时间复杂度：O(n)O(n) 例如：
给定的二叉树是{1,2,3,#,#,4,5}
方法：双栈
图解
算法流程：
- 维护两个栈，一个存放奇数层的节点，一个存放偶数层的节点
- 整型变量level表示当前遍历第几层，奇数则顺序打印，偶数逆序打印, 从第1层开始
- 分奇数层和偶数层处理
- 奇数层按顺序，每次偶数层的栈保存偶数层节点，先存左结点，这样等下次pop时就是右节点先打印
- 偶数层反序，每次奇数层的栈保存偶数层节点，先存右结点，这样等下次pop时就是左节点先打印
代码如下：
给定一个二叉树的根节点root，返回它的中序遍历结果。
数据范围：树上节点数满足 0 \le n \le 10000≤n≤1000，树上每个节点的值满足 0 \le val \le 10000≤val≤1000
进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
示例1
输入：
{1,2,#,#,3} 返回值：
[2,3,1]
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型一维数组
*/
public void preorder(List<Integer> list, TreeNode root){
//遇到空节点则返回
if(root == null)
return;
//去左子树
preorder(list, root.left);
//遍历根节点
list.add(root.val);
//最后去右子树
preorder(list, root.right);
}
public int[] inorderTraversal (TreeNode root) {
// write code here
List<Integer> list = new ArrayList();
//递归前序遍历
preorder(list, root);
//返回的结果
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++)
res[i] = list.get(i);
return res;
}
} 后序遍历同理 求二叉树的层序遍历
1.队列法
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
// 队列保存每一层所有结点
Queue<TreeNode> queue = new LinkedList<>();
// 先放入根节点
queue.offer(root);
while(!queue.isEmpty()) {
// 收集当前层的所有结点的值
ArrayList<Integer> list = new ArrayList<>();
// ·当前层的节点数量
int count = queue.size();
// 遍历每一层
while(count-- > 0) {
// 从对头取出节点
TreeNode node = queue.poll();
// 收集结果
list.add(node.val);
// 左右节点按顺序加到队尾
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
res.add(list);
}
return res;
}
} 2.递归法 import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
DFS(root,res,0);
return res;
}
public void DFS(TreeNode root, ArrayList<ArrayList<Integer>> list, int depth){
// 递归终止条件
if(root == null) {
return;
}
// 初始化集合，该集合用来保存层数为depth时的结点值，depth相当于结果集合list的索引
if(list.size() == depth) {
list.add(new ArrayList<>());
}
// dfs，递归直到叶子节点
DFS(root.left, list, depth + 1);
// 收集层数为depth的结果集
list.get(depth).add(root.val);
DFS(root.right, list, depth + 1);
}
} 按之字形顺序打印二叉树
描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
数据范围：0 \le n \le 15000≤n≤1500,树上每个节点的val满足 |val| <= 1500∣val∣<=1500
要求：空间复杂度：O(n)O(n)，时间复杂度：O(n)O(n)
要求：空间复杂度：O(n)O(n)，时间复杂度：O(n)O(n)
例如：
给定的二叉树是{1,2,3,#,#,4,5}
给定的二叉树是{1,2,3,#,#,4,5}
方法：双栈
图解
算法流程：
- 维护两个栈，一个存放奇数层的节点，一个存放偶数层的节点
- 整型变量level表示当前遍历第几层，奇数则顺序打印，偶数逆序打印, 从第1层开始
- 分奇数层和偶数层处理
- 奇数层按顺序，每次偶数层的栈保存偶数层节点，先存左结点，这样等下次pop时就是右节点先打印
- 偶数层反序，每次奇数层的栈保存偶数层节点，先存右结点，这样等下次pop时就是左节点先打印
import java.util.*;
import java.util.ArrayList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(pRoot == null) {
return res;
}
// 存放奇数层的节点
Stack<TreeNode> stack1 = new Stack<>();
stack1.push(pRoot);
// 存放偶数层的节点
Stack<TreeNode> stack2 = new Stack<>();
int level = 1;
while(!stack1.isEmpty() || !stack2.isEmpty()) {
if(level % 2 != 0) {
ArrayList<Integer> list = new ArrayList<>();
// 奇数层按顺序
while(!stack1.isEmpty()) {
TreeNode node = stack1.pop();
if(node != null) {
// 收集打印结果
list.add(node.val);
// stack2保存偶数层节点，先存左结点，这样等下次pop时就是右节点先打印，满足题目要求
stack2.push(node.left);
stack2.push(node.right);
}
}
// 收集当前层的结果
if(!list.isEmpty()) {
res.add(list);
level++;
}
} else {
// 处理偶数层
ArrayList<Integer> list = new ArrayList<>();
while(!stack2.isEmpty()) {
TreeNode node = stack2.pop();
if(node != null) {
list.add(node.val);
// 需要按顺序push，因为stack1是用在奇数层按顺序输出结果的
stack1.add(node.right);
stack1.add(node.left);
}
}
if(!list.isEmpty()) {
res.add(list);
level++;
}
}
}
return res;
}
}
二叉树的最大深度
描述
求给定二叉树的最大深度，
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。
（注：叶子节点是指没有子节点的节点。）
算法流程：
- 定义递归函数功能：获取root结点的最大深度
- 递归终止条件：root为null
- 返回值：先递归左子结点，再递归右子结点，最后求出每一子树的深度的最大值
代码如下：
public int maxDepth (TreeNode root) {
// write code
if(root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
} 二叉树中和为某一值的路径(一)
描述
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n
例如：
给出如下的二叉树，\ sum=22 sum=22，
返回true，因为存在一条路径 5\to 4\to 11\to 25→4→11→2的节点值之和为 22
方法一：前序遍历
-
这里采用的是前序遍历的递归实现方法，即：根节点-左儿子-右儿子。
-
具体思路如下图所示：
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @param sum int整型
* @return bool布尔型
*/
public boolean hasPathSum (TreeNode root, int sum) {
// 根节点为空，则直接返回false
if (root == null){
return false;
}
// 只有根节点，且值满足要求，则返回true
if (root.left == null && root.right == null && root.val == sum){
return true;
}
// 递归遍历
return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
}
} 二叉搜索树与双向链表
描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
数据范围：输入二叉树的节点数 0 \le n \le 10000≤n≤1000，二叉树中每个节点的值 0\le val \le 10000≤val≤1000
要求：空间复杂度O(1)O(1)（即在原树上操作），时间复杂度 O(n)O(n)
要求：空间复杂度O(1)O(1)（即在原树上操作），时间复杂度 O(n)O(n)
注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出
算法思想：中序遍历优化
解题思路：
对于二叉树进行中序遍历，在遍历的同时调整结点之间的指针，使之成为双向链表 1、特殊情况，二叉树为空，则直接返回 null
2、创建 保留上一个结点 pre，返回链表结点 root
3、递归遍历左子树；root = pRootOfTree
4、遍历当前结点，并修改为双向链表 pRootOfTree.left=pre; pre.right=pRootOfTree;
5、更新 pre = pRootOfTree
6、递归遍历右子树
7、递归结束返回 root
代码展示：
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode pre=null;
TreeNode root=null;
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree==null)
return null;
// 递归遍历左子树
Convert(pRootOfTree.left);
// 判断特殊情况
if (root==null){
root=pRootOfTree;
}
// 修改遍历的结点为双向链表
if (pre!= null){
pRootOfTree.left=pre;
pre.right=pRootOfTree;
}
// 更新 pre
pre=pRootOfTree;
// 递归遍历右子树
Convert(pRootOfTree.right);
return root;
}
} 对称的二叉树
描述
给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
例如： 下面这棵二叉树是对称的
下面这棵二叉树不对称。
例如： 下面这棵二叉树是对称的
下面这棵二叉树不对称。
数据范围：节点数满足 0 \le n \le 10000≤n≤1000，节点上的值满足 |val| \le 1000∣val∣≤1000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
方法：递归（推荐使用）
知识点：二叉树递归
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。
思路：
前序遍历的时候我们采用的是“根左右”的遍历次序，如果这棵二叉树是对称的，即相应的左右节点交换位置完全没有问题，那我们是不是可以尝试“根右左”遍历，按照轴对称图像的性质，这两种次序的遍历结果应该是一样的。
不同的方式遍历两次，将结果拿出来比较看起来是一种可行的方法，但也仅仅可行，太过于麻烦。我们不如在遍历的过程就结果比较了。而遍历方式依据前序递归可以使用递归：
- 终止条件： 当进入子问题的两个节点都为空，说明都到了叶子节点，且是同步的，因此结束本次子问题，返回true；当进入子问题的两个节点只有一个为空，或是元素值不相等，说明这里的对称不匹配，同样结束本次子问题，返回false。
- 返回值： 每一级将子问题是否匹配的结果往上传递。
- 本级任务： 每个子问题，需要按照上述思路，“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，一起进入子问题，需要两边都是匹配才能对称。
具体做法：
- step 1：两种方向的前序遍历，同步过程中的当前两个节点，同为空，属于对称的范畴。
- step 2：当前两个节点只有一个为空或者节点值不相等，已经不是对称的二叉树了。
- step 3：第一个节点的左子树与第二个节点的右子树同步递归对比，第一个节点的右子树与第二个节点的左子树同步递归比较。
图示：
实现代码：
public class Solution {
boolean recursion(TreeNode root1, TreeNode root2){
//可以两个都为空
if(root1 == null && root2 == null)
return true;
//只有一个为空或者节点值不同，必定不对称
if(root1 == null || root2 == null || root1.val != root2.val)
return false;
//每层对应的节点进入递归比较
return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
}
boolean isSymmetrical(TreeNode pRoot) {
return recursion(pRoot, pRoot);
}
}
合并二叉树
描述
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：
两颗二叉树是:
Tree 1
两颗二叉树是:
Tree 1
Tree 2
合并后的树为
数据范围：树上节点数量满足 0 \le n \le 5000≤n≤500，树上节点的值一定在32位整型范围内。
进阶：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n)
方法：递归前序遍历（推荐使用）
知识点：二叉树递归
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。
思路：
要将一棵二叉树的节点与另一棵二叉树相加合并，肯定需要遍历两棵二叉树，那我们可以考虑同步遍历两棵二叉树，这样就可以将每次遍历到的值相加在一起。遍历的方式有多种，这里推荐前序递归遍历。
具体做法：
- step 1：首先判断t1与t2是否为空，若为则用另一个代替，若都为空，返回的值也是空。
- step 2：然后依据前序遍历的特点，优先访问根节点，将两个根点的值相加创建到新树中。
- step 3：两棵树再依次同步进入左子树和右子树。
Java实现代码： public class Solution {
/**
*
* @param t1 TreeNode类
* @param t2 TreeNode类
* @return TreeNode类
*/
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
// write code here
if(t1==null){
return t2;
}
if(t2==null){
return t1;
}
TreeNode head =new TreeNode(t1.val+t2.val);
head.left=mergeTrees(t1.left,t2.left);
head.right=mergeTrees(t1.right,t2.right);
return head;
}
} 二叉树的镜像
描述
操作给定的二叉树，将其变换为源二叉树的镜像。 数据范围：二叉树的节点数 0 \le n \le 10000≤n≤1000 ， 二叉树每个节点的值 0\le val \le 10000≤val≤1000 要求： 空间复杂度 O(n)O(n) 。本题也有原地操作，即空间复杂度 O(1)O(1) 的解法，时间复杂度 O(n)O(n)
比如： 源二叉树
镜像二叉树 
方法：递归前序遍历（推荐使用）
知识点：二叉树递归
代码实现：
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return TreeNode类
*/
public TreeNode Mirror (TreeNode pRoot) {
// write code here
if(pRoot==null){
return pRoot;
}
TreeNode head =new TreeNode(pRoot.val);
head.left=Mirror(pRoot.right);
head.right=Mirror(pRoot.left);
return head;
}
}
判断是不是二叉搜索树
描述
给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点均严格小于当前节点且右子树上的所有节点均严格大于当前节点。 
知识点：二叉树递归
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。
思路：
要将一棵二叉树的节点与另一棵二叉树相加合并，肯定需要遍历两棵二叉树，那我们可以考虑同步遍历两棵二叉树，这样就可以将每次遍历到的值相加在一起。遍历的方式有多种，这里推荐前序递归遍历。
具体做法：
public class Solution {
/**
*
* @param t1 TreeNode类
* @param t2 TreeNode类
* @return TreeNode类
*/
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
// write code here
if(t1==null){
return t2;
}
if(t2==null){
return t1;
}
TreeNode head =new TreeNode(t1.val+t2.val);
head.left=mergeTrees(t1.left,t2.left);
head.right=mergeTrees(t1.right,t2.right);
return head;
}
} 二叉树的镜像
描述
操作给定的二叉树，将其变换为源二叉树的镜像。 数据范围：二叉树的节点数 0 \le n \le 10000≤n≤1000 ， 二叉树每个节点的值 0\le val \le 10000≤val≤1000 要求： 空间复杂度 O(n)O(n) 。本题也有原地操作，即空间复杂度 O(1)O(1) 的解法，时间复杂度 O(n)O(n)
比如： 源二叉树
镜像二叉树 方法：递归前序遍历（推荐使用）
知识点：二叉树递归
操作给定的二叉树，将其变换为源二叉树的镜像。
数据范围：二叉树的节点数 0 \le n \le 10000≤n≤1000 ， 二叉树每个节点的值 0\le val \le 10000≤val≤1000
要求： 空间复杂度 O(n)O(n) 。本题也有原地操作，即空间复杂度 O(1)O(1) 的解法，时间复杂度 O(n)O(n)
比如：
源二叉树
镜像二叉树
代码实现：
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return TreeNode类
*/
public TreeNode Mirror (TreeNode pRoot) {
// write code here
if(pRoot==null){
return pRoot;
}
TreeNode head =new TreeNode(pRoot.val);
head.left=Mirror(pRoot.right);
head.right=Mirror(pRoot.left);
return head;
}
}
判断是不是二叉搜索树
描述
给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点均严格小于当前节点且右子树上的所有节点均严格大于当前节点。
方法（递归）
1.思路整理
判断搜索二叉树（BST）： 考虑搜索二叉树的定义，每一个节点的值应该大于等于左子树中的最大值，小于等于右子树中的最小值。所以我们可以利用递归遍历每一个节点，如果某个节点不满足定义，则不合法，直接返回false。
图解展示：
2.代码实现
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
public boolean isValidBST (TreeNode root) {
// write code here
return BST(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
//left为当前左子树最大值，right为当前右子树最小值
private boolean BST(TreeNode root,long left,long right){
//递归终止条件
if(root==null) return true;
//如果当前节点小于等于左子树节点最大值或者大于等于右子树节点最小值，则不合法
if(root.val<=left||root.val>=right){
return false;
}
//往左子树递归时，left不变，对应右子树由于要考虑当前节点，right变为root.val,同理考虑右子树
return BST(root.left,left,root.val)&&BST(root.right,root.val,right);
}
} 判断是不是完全二叉树
描述
给定一个二叉树，确定他是否是一个完全二叉树。
完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）
数据范围：节点数满足 1 \le n \le 100 \1≤n≤100
样例图1：
方法一：层次遍历
具体方法
使用层次遍历，每一层从左到右遍历节点。
由于判断完全二叉树，当遍历当前层时如果遇到空节点，如果该空节点右侧还有节点，说明该树一定不是完全二叉树，直接返回false，遍历完返回true；
代码实现
public boolean isCompleteTree (TreeNode root) {
// write code here
boolean left = true;
if(root==null){
return true;
}
Queue<TreeNode> queue =new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode nowNode =queue.poll();
if(nowNode==null){
left= false;
}else{
// 遇到空节点直接返回false
if(left == false)
return false;
queue.offer(nowNode.left);
queue.offer(nowNode.right);
}
}
return true;
}
} 判断是不是平衡二叉树
描述
输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
样例解释：
解题思路：
这道题目其实跟二叉树的深度这道题用到的方法是一样的，为什么说是一样的呢？因为我们求二叉树的深度，其实就是求了左右子树的深度的最大值，但是这道题目是要让我们判断二叉树是不是平衡树。
我们都知道如何判断一棵二叉树是不是平衡二叉树，就是它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
所以，这个时候我们只需要判断左右子树的深度之差有没有超过1，若超过了则不是平衡的，反之则为平衡二叉树。
代码如下：
boolean isBalanced = true; // 默认标记为true
public boolean IsBalanced_Solution(TreeNode root) {
TreeDepth(root);
return isBalanced;
}
public int TreeDepth(TreeNode root) {
if(root == null)
return 0; // 递归终止
int l = TreeDepth(root.left);
int r = TreeDepth(root.right);
if(Math.abs(l-r) > 1){
isBalanced = false; // 不是平衡树
}
return Math.max(l,r)+1; // 求深度
} 二叉搜索树的最近公共祖先
描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
思路：
我们也可以利用二叉搜索树的性质：对于某一个节点若是p与q都小于等于这个这个节点值，说明p、q都在这个节点的左子树，而最近的公共祖先也一定在这个节点的左子树；若是p与q都大于等于这个节点，说明p、q都在这个节点的右子树，而最近的公共祖先也一定在这个节点的右子树。而若是对于某个节点，p与q的值一个大于等于节点值，一个小于等于节点值，说明它们分布在该节点的两边，而这个节点就是最近的公共祖先，因此从上到下的其他祖先都将这个两个节点放到同一子树，只有最近公共祖先会将它们放入不同的子树，每次进入一个子树又回到刚刚的问题，因此可以使用递归。
具体做法：
- step 1：首先检查空节点，空树没有公共祖先。
- step 2：对于某个节点，比较与p、q的大小，若p、q在该节点两边说明这就是最近公共祖先。
- step 3：如果p、q都在该节点的左边，则递归进入左子树。
- step 4：如果p、q都在该节点的右边，则递归进入右子树。
import java.util.*;
public class Solution {
public int lowestCommonAncestor (TreeNode root, int p, int q) {
//空树找不到公共祖先
if(root == null)
return -1;
//pq在该节点两边说明这就是最近公共祖先
if((p >= root.val && q <= root.val) || (p <= root.val && q >= root.val))
return root.val;
//pq都在该节点的左边
else if(p <= root.val && q <= root.val)
//进入左子树
return lowestCommonAncestor(root.left, p, q);
//pq都在该节点的右边
else
//进入右子树
return lowestCommonAncestor(root.right, p, q);
}
}
在二叉树中找到两个节点的最近公共祖先
在二叉树中找到两个节点的最近公共祖先
描述
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
数据范围：树上节点数满足 1 \le n \le 10^5 \1≤n≤105 , 节点值val满足区间 [0,n)
要求：时间复杂度 O(n)O(n)
递归写法
public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
return helper(root, o1, o2).val;
}
public TreeNode helper(TreeNode root, int o1, int o2) {
if (root == null || root.val == o1 || root.val == o2)
return root;
TreeNode left = helper(root.left, o1, o2);
TreeNode right = helper(root.right, o1, o2);
//如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果即可
if (left == null)
return right;
//同上
if (right == null)
return left;
//如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
//我们只需要返回cur结点即可。
return root;
}
#二叉树##之字形打印二叉树#
投递美团等公司10个岗位 >
