重建二叉树
根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
- 利用栈循环解决
极为复杂，可以跳过此方法。
- 通过循环一次前序，完成树的的构建。
- 根节点直接插入，返回的对象，就是根节点。
- 前序相邻的2个数，只能是上一个节点的左右节点，或者是祖先节点的右节点。
前序：根左右；中序：左根右。 - 4个参数进行处理。
a. 需要被插入新树的处理树cur，插入根节点后，直接指向。
b. 准备插入别人的新树，用下标 i 来表示前序遍历的情况。
c. 用来确定新树存放的具体位置的，中序遍历 j 。
d. 用于查找对应祖先的栈。 - 如果当前处理树和中序遍历的值不同，将新树直接插入左子树，值入栈。
- 如果当前处理树和中序遍历相同，说明新树存放的位置一定不为当前树的左边。此时 j++，再查看栈和中序遍历的情况。
- 若栈顶与中序相同，说明为祖先节点的右节点，此时需要找到对应的祖先节点。j++，同时出栈。当前处理树指向从栈顶弹出的祖先。直至栈为空，或者栈顶与中序遍历值不同。然后插入新树至当前处理树的右节点。
- 若不同，则直接插入至当前处理树的右节点。
import java.util.*;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
int n = pre.length;
int m = vin.length;
//每个遍历都不能为0
if(n == 0 || m == 0)
return null;
Stack<TreeNode> s = new Stack<TreeNode>();
//首先建立前序第一个即根节点
TreeNode root = new TreeNode(pre[0]);
TreeNode cur = root;
for(int i = 1, j = 0; i < n; i++){
//要么旁边这个是它的左节点
if(cur.val != vin[j]){
cur.left = new TreeNode(pre[i]);
s.push(cur);
//要么旁边这个是它的右节点，或者祖先的右节点
cur = cur.left;
}else{
j++;
//弹出到符合的祖先
while(!s.isEmpty() && s.peek().val == vin[j]){
cur = s.pop();
j++;
}
//添加右节点
cur.right = new TreeNode(pre[i]);
cur = cur.right;
}
}
return root;
}
}
- 递归
答案挺多的，思路都一样。
将前序的第一个数，在中序里面划分成两个部分。然后每个部分重复上述过程，形成递归。
//作者：道阻且长z
import java.util.Arrays;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
//递归调用的终止条件
if(pre.length == 0 || in.length == 0){
return null;
}
//由前序遍历得到该二叉树的根结点
TreeNode root = new TreeNode(pre[0]);
//在中序遍历中找根结点位置，进行左右子树的划分
for(int i = 0; i < in.length; i++){
if(root.val == in[i]) {
//将左子树看成一棵二叉树调用该方法，可以得到左子树根结点，即上面根结点的左子结点
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
//将右子树看成一棵二叉树调用该方法，可以得到右子树根结点，即上面根结点的右子结点
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
//找到根结点位置便跳出循环
break;
}
}
//返回根结点
return root;
}
}
二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回 。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
- 递归
- 设置一个TreeLinkNode类型的ArrayList，里面放中序遍历的树。
- 先获取头节点。
- 利用递归，将整棵树拆分成中序遍历，放入数组中。
- 比较输出。
if(root != null) {
InOrder(root.left);
nodes.add(root);
InOrder(root.right);
}
- 迭代
- 有右子树，找右子树中的最左节点。
- 无右子树，找第一个左链指向，包含该节点的祖先节点。
树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
- 递归
- 可以理解为3个模块。当前root为子结构，root左边有子结构，root右边有子结构。
- 左边或者右边有子结构可以用当前函数递归，重点是如何判断当前root下为子结构。
- 子结构的root为null时，说明存在此子结构，返回true。原树的root为null时，说明不存在，返回false。值不一样，返回false。然后分别判断2棵树对应的左右子树，形成递归。
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null)
return false;
return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}
private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {
if (root2 == null)
return true;
if (root1 == null)
return false;
if (root1.val != root2.val)
return false;
return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);
}
二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
- 辅助栈处理
将左右子树放到栈里面，然后弹出形成反向，再插入。
原来：左：A树 ---右：B树
入栈：A--B；出栈：B--A；
插入：左：B树---右：A树 - 优-递归
将左右子树交换，一眼递归。
public TreeNode Mirror (TreeNode pRoot) {
// write code here
return this.fine(pRoot);
}
public TreeNode fine(TreeNode temp){
if(temp==null){
//对象为null
return temp;
}
//交换左右子树
TreeNode tree = null;
tree = temp.left;
temp.left = temp.right;
temp.right = tree;
fine(temp.left);
fine(temp.right);
return temp;
}
对称的二叉树
给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
- 递归
这棵树的左子树和右子树是否对称。看左子树的左节点和右子树的右节点是否对称，形成递归。看最后节点是否相同。
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot==null){
return true;
}
return this.fine(pRoot.left,pRoot.right);
}
boolean fine(TreeNode treeL,TreeNode treeR){
if(treeL==null&&treeR==null){
return true;
}else if(treeL==null||treeR==null){
return false;
}else if(treeL.val!=treeR.val){
return false;
}else{
return (fine(treeL.left,treeR.right)&&fine(treeL.right,treeR.left));
}
}
从上往下打印二叉树
不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。
- 队列
- 从左到右按行依次输出。所以在遍历的时候，很希望将顺序确定。而这个顺序显然是先进先出。用队列处理。
- 出去一个树的节点，就将这个树的左右子树顺序加到队列中去。
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> res = new ArrayList();
//队列的表示方法
Queue<TreeNode> q = new LinkedList<>();
if(root==null){
return res;
}
q.add(root);
while(!q.isEmpty()){
res.add(q.peek().val);
if(q.peek().left!=null){
q.add(q.peek().left);
}
if(q.peek().right!=null){
q.add(q.peek().right);
}
q.poll();
}
return res;
}
把二叉树打印成多行
给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。
- 队列
与上题差不多。但是需要增加一个树高的判断。当第一次进入队列的时候，当前队列的数据，一定是同一树高的。所以对其的大小进行记录。并在后续处理中，将此大小不断循环减一，直至0跳出循环。
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
int cnt = queue.size();
while (cnt-- > 0) {
TreeNode node = queue.poll();
if (node == null)
continue;
list.add(node.val);
queue.add(node.left);
queue.add(node.right);
}
if (list.size() != 0)
ret.add(list);
}
return ret;
}
- 递归
要将数据按行存储，那么先存储第一行，再存储左子树以及右子树的第一行，形成递归。关键在于树的高度对数组的影响。
//官方递归解
import java.util.*;
public class Solution {
private void traverse(TreeNode root, ArrayList<ArrayList<Integer> > res, int depth) {
if(root != null){
//数组长度小于当前层数，新开一层
if(res.size() < depth)
res.add(new ArrayList<Integer>());
//数组从0开始计数因此减1，在节点当前层的数组中插入节点
res.get(depth - 1).add(root.val);
//递归左右时节点深度记得加1
traverse(root.left, res, depth + 1);
traverse(root.right, res, depth + 1);
}
}
//层次遍历
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
//树的层级从1开始递归计数
traverse(pRoot, res, 1);
return res;
}
}
按之字形顺序打印二叉树
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
- 官方推荐-队列
- 用Collections.reverse(list);对ArrayList反转即可。
- 增加一个boolean变量，判断是奇数层还是偶数层。关键代码同上。
- 双栈
- 树高奇偶不同，输出相反。
- 树高为基时，其子树按先左再右入栈。树高为偶时，子树按先右再左入栈。
- 因为栈为空是进行下一层的判断条件，所以可以直接先定义两个栈，一个处理基树高，一个处理偶树高。
import copy
class Solution:
def Print(self , pRoot: TreeNode) -> List[List[int]]:
head = pRoot
res = []
if not head:
# 如果是空，则直接返回空list
return res
s1, s2 = [], []
# 放入第一次
s1.append(head)
while s1 or s2:
temp = []
# 遍历奇数层
while s1:
node = s1[-1]
# 记录奇数层
temp.append(node.val)
# 奇数层的子节点加入偶数层
if node.left:
s2.append(node.left)
if node.right:
s2.append(node.right)
s1.pop()
# 数组不为空才添加
if len(temp):
res.append(copy.deepcopy(temp))
# 清空本层数据
temp.clear()
# 遍历偶数层
while s2:
node = s2[-1]
# 记录偶数层
temp.append(node.val)
# 偶数层的子节点加入奇数层
if node.right:
s1.append(node.right)
if node.left:
s1.append(node.left)
s2.pop()
if len(temp):
res.append(temp)
return res
