大量的二叉树题。。其实本质都是二叉树遍历的思路，需要掌握的基础知识是二叉树的先中后序遍历，然后再会个非递归的层序遍历，非递归的先序遍历，应该可以解决大部分问题。
层序两道
分行从上到下打印二叉树
就是在层序遍历的基础上把每一层分行打出来，做的改进就是使用两个变量，一个变量来记录将要打印的下一层的节点数，另一个变量记录本层还未打印完的节点数。前者在入队时候进行更新，后者在出队时候进行更新，当本层还未打印完的节点为0时，把下一层要打印的节点数赋值给它，下一层的变量再归零即可。代码如下：
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
if(pRoot == null){
return new ArrayList<ArrayList<Integer>>();
}
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(pRoot);
int toBePrinted = 1;
int nextLineToBePrinted = 0;
ArrayList<Integer> newLine = new ArrayList<>();
while(!queue.isEmpty()){
TreeNode node = queue.poll();
newLine.add(node.val);
toBePrinted --;
if(node.left != null){45r45
queue.offer(node.left);
nextLineToBePrinted ++;
}
if(node.right != null){
queue.offer(node.right);
nextLineToBePrinted ++;
}
if(toBePrinted == 0){
ret.add(newLine);
toBePrinted = nextLineToBePrinted;
nextLineToBePrinted = 0;
newLine = new ArrayList<>();
}
}
return ret;
}
下面也是一种更为优雅的解法，不用去记录这一行下一行。
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
if(pRoot == null){
return new ArrayList<>();
}
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(pRoot);
ArrayList<Integer> newLine;
while(!queue.isEmpty()){
newLine = new ArrayList<>();
int l = queue.size();
while(l -- > 0){
TreeNode node = queue.poll();
newLine.add(node.val);
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
ret.add(newLine);
}
return ret;
之字型打印
这个题名字起的。。我感觉叫弓字形也行，但名字无所谓了。。
这实际上还是层序遍历的变种，只不过不再是我们用先进先出的队列就能做到了。它符合栈的特点，而且我们需要两个栈来做这个事情。没有太多想分析的，动笔写几下应该就能发现规律，奇数行和偶数行左右节点入栈的顺序是不一样的。
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
if(pRoot == null){
return new ArrayList<ArrayList<Integer>>();
}
Stack<TreeNode> currentStack = new Stack<>();
Stack<TreeNode> nextStack = new Stack<>();
currentStack.push(pRoot);
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
ArrayList<Integer> newLine = new ArrayList<>();
int line = 1;
while((!currentStack.isEmpty())||(!nextStack.isEmpty())){
TreeNode node = currentStack.pop();
newLine.add(node.val);
if((line & 1)==1){
if(node.left != null){
nextStack.push(node.left);
}
if(node.right != null){
nextStack.push(node.right);
}
}else{
if(node.right != null){
nextStack.push(node.right);
}
if(node.left != null){
nextStack.push(node.left);
}
}
if(currentStack.isEmpty()){
ret.add(newLine);
currentStack = nextStack;
nextStack = new Stack<>();
newLine = new ArrayList<>();
line ++;
}
}
return ret;
}
先序
下面这些题，看似是与遍历没有半毛钱关系，但是本质上还是在遍历的过程中动一些手脚，不想我们常规遍历时候去print，而是有了其他略微复杂的操作。
二叉树的镜像
就是在先序遍历时候，把左右子树交换一下即可：
public void Mirror(TreeNode root) {
if(root == null){
return;
}
if(root.left == null && root.right == null){
return;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
Mirror(root.left);
Mirror(root.right);
}
对称二叉树
对称不对称，还是看遍历的序列，我们熟悉先序遍历，那么如果把先序遍历反过来，先根后右再左，那么一个对称的二叉树，先序和反先序遍历的序列将会是相同的。我们可以轻易写出以下代码：
boolean isSymmetrical(TreeNode pRoot){
return isSymmetrical(pRoot,pRoot);
}
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);
}
}
树的子结构
可以理解成是两棵树在同时遍历，只不过先要递归找到值相同的节点，会比单纯的遍历复杂一些。
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean res = false;
//当Tree1和Tree2都不为空的时候，才进行比较。否则直接返回false
if(root1!=null && root2 != null){
if(root1.val == root2.val){//如果找到了对应Tree2的根节点的点
res = reallyHasRoot2(root1,root2);
}
if(!res){//如果找不到，那么就再去root的左儿子当作起点，去判断是否包含Tree2
res = HasSubtree(root1.left,root2);
}
if(!res){//如果还找不到，那么就再去root的右儿子当作起点，去判断是否包含Tree2
res = HasSubtree(root1.right,root2);
}
}
return res;
}
private boolean reallyHasRoot2(TreeNode root1, TreeNode root2){
if(root2 == null){//如果Tree2已经遍历完了都能对应的上，返回true
return true;
}
if(root1 == null){//如果Tree2还没有遍历完，Tree1却遍历完了。返回false
return false;
}
if(!(root1.val == root2.val)){//如果其中有一个点没有对应上，返回false
return false;
}
//如果根节点对应的上，那么就分别去子节点里面匹配
return reallyHasRoot2(root1.left,root2.left) && reallyHasRoot2(root1.right,root2.right);
}
}
二叉树中和为某一值的路径
这个题本质上还是去遍历，遍历过程中有个变量记录和，如果和符合条件，并且是叶子节点，那就找到了一条路径。写代码注意的点是，要通过一个容器把走过的路保存下来，然后返回之前记得
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null || target == 0){
return ans;
}
ArrayList<Integer> list = new ArrayList<>();
FindPath(root, target, list, 0);
return ans;
}
public void FindPath(TreeNode root, int target, ArrayList<Integer> list, int currentSum){
currentSum += root.val;
list.add(root.val);
if(currentSum == target && root.left == null && root.right == null){
ans.add(new ArrayList<>(list));
}
if(root.left != null){
FindPath(root.left, target, list, currentSum);
}
if(root.right != null){
FindPath(root.right, target, list, currentSum);
}
list.remove(list.size()-1);
}
BST的中序
之所以把中序列出来，就是因为中序遍历序列一个最大的特点就是，它是BST中节点排好序的有序序列。
BST的第K小节点
原题叫第K大，但总感觉题意是第K小。所以改过来了。这个题本质上还是去做一个中序遍历，遍历过程中有一个计数器值是K，每次中序遍历到时候，就给k--，k=1的时候，正好就是要找的目标节点。
int k;
TreeNode KthNode(TreeNode pRoot, int k){
if(pRoot == null){
return null;
}
this.k = k;
return KthNodeCore(pRoot);
}
TreeNode KthNodeCore(TreeNode pRoot){
TreeNode target = null;
if(pRoot.left != null){
target = KthNodeCore(pRoot.left);
}
if(target == null){
if(k == 1){
target = pRoot;
}
k --;
}
if(target == null && pRoot.right != null){
target = KthNodeCore(pRoot.right);
}
return target;
}
给序列反推
BST的后序遍历序列
要对后序序列的特点熟悉，递归去求解左右子树是否为BST。这个序列还可以换成先序，根据先序的序列特点去写，就不再详细叙述了。
public boolean VerifySequenceOfBST(int [] sequence, int start, int r){
if(start >= r){
return true;
}
int root = sequence[r];
int i;
for(i = start; i <= r-1; i++){
if(sequence[i] > root){
break;
}
}
int j;
for(j = i; j <=r-1; j++){
if(sequence[j] < root){
return false;
}
}
return VerifySequenceOfBST(sequence, start, i - 1) && VerifySequenceOfBST(sequence, i, r -1);
}
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length == 0){
return false;
}
return VerifySequenceOfBST(sequence, 0, sequence.length-1);
}
明天补充根据序列重建BST的题目。
网友评论