题目链接：
JZ7 重建二叉树
题目描述
：给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
前提条件：
pre 和 vin 均无重复元素
vin出现的元素均出现在 pre里
只需要返回根结点，系统会自动输出整颗树做答案对比
要求：空间复杂度 O(n)，时间复杂度 O(n)
题目分析
：已知
前序遍历和中序遍历可以唯一确定一棵二叉树
，前序遍历可以首先确定root结点，在中序遍历中找到root结点值的下标，就可以划分左右子树结点集合，以此类推，递归遍历。
递归函数功能：原函数功能（根据前序数组和中序数组重建二叉树）
递归出口：pre.length为0 或 vin.length为0
递归入口：在中序遍历数组中找到当前root值的索引，通过
Arrays.copyOfRange()
函数传pre数组和vin数组
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
//重建二叉树
if(pre.length==0||vin.length==0){
return null;
}
TreeNode root = new TreeNode(pre[0]); //根节点
for(int i=0; i<vin.length; i++){
if(vin[i]==pre[0]){
//递归左子树
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));
//递归右子树
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(vin,i+1,vin.length));
}
}
return root;
}
}
题目链接：
JZ54 二叉搜索树的第k个节点
题目描述
：给定一棵结点数为n
二叉搜索树
，请找出其中的
第 k 小
的TreeNode结点值。不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1。
题目分析
：
①
递归遍历
。二叉搜索树左中右遍历值依次从小到大，所以我们在中序遍历的基础上，增加遍历结点个数count的限制，返回第k个最小结点。时间复杂度为O(n)， 空间复杂度为O(n)；
public class Solution {
//指向目标结点（第k个的结点）
TreeNode res = null;
//记录遍历过的结点（从最小的结点开始遍历）
private int count = 0;
//中序遍历
public void midOrder(TreeNode root, int k){
if(root==null || count>k){
return;
}
midOrder(root.left,k);
count++;
if(count==k){
res = root; //标记第k个结点
}
midOrder(root.right,k);
}
public int KthNode (TreeNode proot, int k) {
midOrder(proot, k);
if(res != null){
return res.val;
}
//二叉树为null,或第k个结点找不到
return -1;
}
}
②
非递归中序遍历
，采用数据结构
栈
进行存储结点。
import java.util.*;
public class Solution {
public int KthNode (TreeNode proot, int k) {
//非递归中序遍历
if(proot==null) return -1;
int count = 0;
TreeNode res = null;
Stack<TreeNode> s = new Stack<TreeNode>();
while(proot!=null || !s.isEmpty()){
while(proot!=null){
s.push(proot);
proot = proot.left;
}
TreeNode temp = s.pop();
count++;
if(count==k){
res = temp;
break;
}
proot = temp.right;
}
if(res!=null){
return res.val;
}
return -1;
}
}
题目链接：
JZ26 树的子结构
题目描述
：输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，
题目分析
：采用递归比较方便，主要思路为：
1.先判断A/B任意一个根节点是否为空，边界条件。有null，直接返回false
2.两个根节点都不为空，则判断A B两棵树是否相同isSame()函数，
①递归条件：A B当前结点值相等，继续遍历其左右子树
②终止条件：先判断B，如果B遍历到叶子结点，则遍历结束返回true；如果B遍历到不为null的结点，A为null了，则返回false
3.如果当前结点对应的两棵树不相同，则递归遍历判断A.left和A.right分别与B是否为A⊇B的关系。
public class Solution {
public boolean isSame(TreeNode root1, TreeNode root2){
//递归终止条件：先判断B，如果B遍历到叶子结点，则遍历结束返回true
if(root2==null) return true;
//如果B遍历到不为null的结点，A为null了，则返回false
if(root1==null) return false;
//A B当前结点值相等，继续遍历其左右子树
if(root1.val==root2.val){
return isSame(root1.left,root2.left) && isSame(root1.right, root2.right);
}
//没找到相同的子结构
return false;
}
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
//根节点三种情况返回false：root1 root2为空,root1为空root2不为空，root1不为空root2为空
if(root1==null || root2==null){
return false;
}
return isSame(root1, root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
}
}
题目链接：
JZ27 二叉树的镜像
题目描述
：操作给定的二叉树，将其变换为源二叉树的镜像。
数据范围：二叉树的节点数 0
≤
\le
≤
n
≤
\le
≤
1000， 二叉树每个节点的值 0
≤
\le
≤
val
≤
\le
≤
1000
要求： 空间复杂度 O(n) 。本题也有原地操作，即空间复杂度 O(1) 的解法，时间复杂度 O(n)
题目分析
：①
递归
依次交换左右子树。 时间复杂度为O(n)，空间复杂度为O(1)。
public class Solution {
public TreeNode temp = null;
public TreeNode Mirror (TreeNode pRoot) {
if(pRoot==null) return pRoot;
//遍历到叶子节点的情况
if(pRoot.left==null && pRoot.right==null){
return pRoot;
}
//交换节点
temp = pRoot.left;
pRoot.left = pRoot.right;
pRoot.right = temp;
//递归遍历
Mirror(pRoot.left);
Mirror(pRoot.right);
return pRoot;
}
}
②
非递归
遍历，交换左右子树。 时间复杂度为O(n)，空间复杂度为O(n)。
public class Solution {
public TreeNode Mirror (TreeNode pRoot) {
if(pRoot==null) return null;
Stack<TreeNode> s = new Stack<>();
s.push(pRoot);
while(!s.isEmpty()){
TreeNode top = s.pop();
TreeNode temp = top.right;
top.right = top.left;
top.left = temp;
if(top.right!=null){
s.push(top.right);
}
if(top.left!=null){
s.push(top.left);
}
}
return pRoot;
}
}
题目链接：
JZ32 从上往下打印二叉树
题目描述
：不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)
题目分析
：
①
非递归实现
二叉树层序遍历 (队列)
import java.util.*;
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
//二叉树的层序遍历
ArrayList<Integer> res = new ArrayList<Integer>();
if(root==null) return res;
Deque<TreeNode> q = new ArrayDeque<TreeNode>();
q.offerLast(root);
res.add(root.val);
while(root!=null && !q.isEmpty()){
TreeNode top = q.pollFirst();
if(top.left!=null){
q.offerLast(top.left);
res.add(top.left.val);
}
if(top.right!=null){
q.offerLast(top.right);
res.add(top.right.val);
}
}
return res;
}
}
②
递归实现
二叉树层序遍历。采用二维列表数组记录每一层的结点值，最后再将值打印至一维列表中。
我们需要通过
记录层数
来建立二维列表中的每一行。具体代码如下：
public class Solution {
//递归调用函数
public void recursion(TreeNode root, ArrayList<ArrayList<Integer>> list, int depth){
if(root!=null){
if(list.size() < depth){
ArrayList<Integer> row = new ArrayList<>(); //新的行
row.add(root.val); //添加每一行的第一个元素
list.add(row); //将该行添加至二维数组中
}else{
//添加该行的其他元素
ArrayList<Integer> row = list.get(depth-1);
row.add(root.val);
}
}else{
return;
}
recursion(root.left,list,depth+1);
recursion(root.right,list,depth+1);
}
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
//DFS 递归实现
ArrayList<Integer> res = new ArrayList<>();
//二维列表
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
if(root==null){
return res;
}
recursion(root,list,1);
for(int i=0; i<list.size();i++){
for(int j=0;j<list.get(i).size();j++){
res.add(list.get(i).get(j));
}
}
return res;
}
}