未完待续
/**
* 二叉树节点类
* @author Administrator
*
*/
public class BinaryTreeNode {
public Integer data; // data
public BinaryTreeNode leftNode; // 左孩子
public BinaryTreeNode rightNode; // 右孩子
}
package com.binarytree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
/**
*
* TODO: 一定要能熟练地写出所有问题的递归和非递归做法！
*
* 1. 求二叉树中的节点个数: getNodeNumRec（递归），getNodeNum（迭代）
* 2. 求二叉树的深度: getDepthRec（递归），getDepth
* 3. 前序遍历，中序遍历，后序遍历: preorderTraversalRec, preorderTraversal, inorderTraversalRec, postorderTraversalRec
* (https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_2)
* 4.分层遍历二叉树（按层次从上往下，从左往右）: levelTraversal, levelTraversalRec（递归解法！）
* 5. 将二叉查找树变为有序的双向链表: convertBST2DLLRec, convertBST2DLL
* 6. 求二叉树第K层的节点个数：getNodeNumKthLevelRec, getNodeNumKthLevel
* 7. 求二叉树中叶子节点的个数：getNodeNumLeafRec, getNodeNumLeaf
* 8. 判断两棵二叉树是否相同的树：isSameRec, isSame
* 9. 判断二叉树是不是平衡二叉树：isAVLRec
* 10. 求二叉树的镜像（破坏和不破坏原来的树两种情况）：mirrorRec, mirrorCopyRec
* 10.1 判断两个树是否互相镜像：isMirrorRec
* 11. 求二叉树中两个节点的最低公共祖先节点：getLastCommonParent, getLastCommonParentRec, getLastCommonParentRec2
* 12. 求二叉树中节点的最大距离：getMaxDistanceRec
* 13. 由前序遍历序列和中序遍历序列重建二叉树：rebuildBinaryTreeRec
* 14.判断二叉树是不是完全二叉树：isCompleteBinaryTree, isCompleteBinaryTreeRec
*
*/
public class BinaryTreeSummary {
/**
* 递归前序遍历
* @param root
*/
public static void preOrderRec(BinaryTreeNode root){
if(root != null) {
System.out.print(root.data+" ");
preOrderRec(root.leftNode);
preOrderRec(root.rightNode);
}
}
/**
* 非递归前序遍历
* @param root
*/
public static void preOrder(BinaryTreeNode root){
Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
BinaryTreeNode p = root;
while(p!=null || s.size()>0) {
if(p!=null) {
System.out.print(p.data+" ");
s.push(p);
p = p.leftNode;
}
else {
p = s.pop();
p = p.rightNode;
}
}
}
/**
* 非递归中序遍历
* @param root
*/
public static void inOrder(BinaryTreeNode root) {
Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
BinaryTreeNode p = root;
while(p!=null || s.size()>0) {
if(p!=null) {
s.push(p);
p = p.leftNode;
}
else {
p = s.pop();
System.out.print(p.data+" ");
p = p.rightNode;
}
}
}
/**
* 递归中序遍历
* @param root
*/
public static void inOrderRec(BinaryTreeNode root) {
if(root != null) {
inOrderRec(root.leftNode);
System.out.print(root.data+" ");
inOrderRec(root.rightNode);
}
}
/**
* 非递归层次遍历二叉树
* 队列实现
* @param root
*/
public static void printTreeFromTopToBottom(BinaryTreeNode root) {
Queue<BinaryTreeNode> q = new LinkedList<BinaryTreeNode>();
q.add(root);
while(q.size() > 0) {
BinaryTreeNode node = q.poll();
System.out.print(node.data+" ");
if(node.leftNode != null) {
q.add(node.leftNode);
}
if(node.rightNode != null) {
q.add(node.rightNode);
}
}
}
/**
* 递归层次遍历二叉树
* @param root
*/
public static void printTreeFromTopToBottomRec(BinaryTreeNode root) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
dfs(root, 0, ret);
System.out.println(ret);
}
private static void dfs(BinaryTreeNode root, int level, ArrayList<ArrayList<Integer>> ret){
if(root == null){
return;
}
// 添加一个新的ArrayList表示新的一层
if(level >= ret.size()){
ret.add(new ArrayList<Integer>());
}
ret.get(level).add(root.data); // 把节点添加到表示那一层的ArrayList里
dfs(root.leftNode, level+1, ret); // 递归处理下一层的左子树和右子树
dfs(root.rightNode, level+1, ret);
}
/**
* 重建二叉树
* @param preOrder
* @param inOrder
* @return
*/
public static BinaryTreeNode rebuildBinaryTree(List<Integer> preOrder, List<Integer> inOrder ) {
BinaryTreeNode root = null;
List<Integer> leftPreOrder;
List<Integer> rightPreOrder;
List<Integer> leftInorder;
List<Integer> rightInorder;
int inorderPos;
int preorderPos;
if ((preOrder.size() != 0) && (inOrder.size() != 0))
{
// 把preorder的第一个元素作为root
root = new BinaryTreeNode();
root.data = preOrder.get(0);
// Based upon the current node data seperate the traversals into leftPreorder, rightPreorder,
// leftInorder, rightInorder lists
// 因为知道root节点了，所以根据root节点位置，把preorder，inorder分别划分为 root左侧 和 右侧 的两个子区间
inorderPos = inOrder.indexOf(preOrder.get(0)); // inorder序列的分割点
leftInorder = inOrder.subList(0, inorderPos);
rightInorder = inOrder.subList(inorderPos + 1, inOrder.size());
preorderPos = leftInorder.size(); // preorder序列的分割点
leftPreOrder = preOrder.subList(1, preorderPos + 1);
rightPreOrder = preOrder.subList(preorderPos + 1, preOrder.size());
root.leftNode = BinaryTreeSummary.rebuildBinaryTree(leftPreOrder, leftInorder); // root的左子树就是preorder和inorder的左侧区间而形成的树
root.rightNode = BinaryTreeSummary.rebuildBinaryTree(rightPreOrder, rightInorder); // root的右子树就是preorder和inorder的右侧区间而形成的树
}
return root;
}
/**
* 二叉树的镜像
* @param root
*/
public static void MirrorBinaryTree(BinaryTreeNode root) {
if(root != null) {
if(root.leftNode!=null || root.rightNode!=null) {
BinaryTreeNode x = new BinaryTreeNode();
x = root.leftNode;
root.leftNode = root.rightNode;
root.rightNode = x;
MirrorBinaryTree(root.rightNode);
MirrorBinaryTree(root.leftNode);
}
}
}
/**
* 递归求二叉树的节点个数
* @param root
* @return
*/
public static int getNodeNumRec(BinaryTreeNode root) {
if(root == null) {
return 0;
}
return getNodeNumRec(root.leftNode) + getNodeNumRec(root.rightNode) + 1;
}
/**
* 非递归求二叉树的节点个数
* 通过队列进行层次遍历
* @param root
* @return
*/
public static int getNodeNum(BinaryTreeNode root) {
int num=0;
Queue<BinaryTreeNode> q = new LinkedList<BinaryTreeNode>();
q.add(root);
while(q.size() > 0) {
BinaryTreeNode node = q.poll();
num++;
if(node.leftNode != null) {
q.add(node.leftNode);
}
if(node.rightNode != null) {
q.add(node.rightNode);
}
}
return num;
}
/**
* 递归求二叉树的深度
* @param root
* @return
*/
public static int getDepthRec(BinaryTreeNode root) {
if(root == null ) {
return 0;
}
return Math.max(getDepthRec(root.leftNode)+1, getDepthRec(root.rightNode)+1);
}
/**
* 非递归求二叉树的深度
* 队列层次遍历，遍历一层depth++
* @param root
* @return
*/
public static int getDepth(BinaryTreeNode root) {
int depth=0;
int currentLevelNodeNums = 1;
int nextLevelNodeNums = 0;
Queue<BinaryTreeNode> q = new LinkedList<BinaryTreeNode>();
if(root == null ) {
return 0;
}
q.add(root);
while(q.size() > 0) {
BinaryTreeNode node = q.poll(); // 去除一个节点
currentLevelNodeNums--; // 当前层数节点减少一个
if(node.leftNode != null) {
q.add(node.leftNode);
nextLevelNodeNums++;
}
if(node.rightNode != null) {
q.add(node.rightNode);
nextLevelNodeNums++;
}
if(currentLevelNodeNums == 0) { // 当前层节点数为0 当前层遍历完成
depth++;
currentLevelNodeNums = nextLevelNodeNums;
nextLevelNodeNums = 0;
}
}
return depth;
}
/**
* 求二叉树第k层的节点个数
* @param root
* @param k
* @return
*/
public static int getNodeNumKthLevel(BinaryTreeNode root, int k) {
int currentLevel = 1;
int nextLevelNodesNum = 0;
int currentNodesNum = 1;
Queue<BinaryTreeNode> s = new LinkedList<BinaryTreeNode>();
if(root == null) {
return 0;
}
s.add(root);
while( s.size()>0 && currentLevel<k) {
BinaryTreeNode node = s.poll();
currentNodesNum--;
if(node.leftNode!=null) {
s.add(node.leftNode);
nextLevelNodesNum++;
}
if(node.rightNode!=null) {
s.add(node.rightNode);
nextLevelNodesNum++;
}
if(currentNodesNum == 0) {
currentLevel++; // 进入下一层
currentNodesNum = nextLevelNodesNum;
nextLevelNodesNum = 0;
}
}
return currentNodesNum;
}
public static void main(String[] args) {
/* 3
* 2 5
* 1 * 4 6
*/
BinaryTreeNode x = new BinaryTreeNode();
x.data = 3;
x.leftNode = new BinaryTreeNode();
x.leftNode.data = 2;
x.rightNode = new BinaryTreeNode();
x.rightNode.data = 5;
x.rightNode.leftNode = new BinaryTreeNode();
x.rightNode.leftNode.data = 1;
x.rightNode.rightNode = new BinaryTreeNode();
x.rightNode.rightNode.data = 6;
x.leftNode.leftNode = new BinaryTreeNode();
x.leftNode.leftNode.data = 4;
// BinaryTreeSummary.MirrorBinaryTree(x);
// System.out.println();
// System.out.println(x.toString());
// BinaryTreeSummary.printTreeFromTopToBottom(x);
// System.out.println("asd");
System.out.println("Start");
System.out.println(BinaryTreeSummary.getNodeNumKthLevel(x, 0));
System.out.println("End");
}
// List<Integer> x = new ArrayList<Integer>();
// List<Integer> y = new ArrayList<Integer>();
// x.add(1);x.add(2);x.add(4);x.add(7);x.add(3);x.add(5);x.add(6);x.add(8);
// y.add(4);y.add(7);y.add(2);y.add(1);y.add(5);y.add(3);y.add(8);y.add(6);
// BinaryTreeNode z = BinaryTreeSummary.rebuildBinaryTree(x,y);
// System.out.println(z.toString());
// System.out.println();
// }
}
