面试大总结之二：Java搞定面试中的二叉树题目(二)
y(r1);
// inorderTraversal(mirrorRoot);
System.out.println(isCompleteBinaryTree(r1));
System.out.println(isCompleteBinaryTreeRec(r1));
}
private static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
/**
* 求二叉树中的节点个数递归解法： O(n)
* （1）如果二叉树为空，节点个数为0
* （2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 +
* 右子树节点个数 + 1
*/
public static int getNodeNumRec(TreeNode root) {
if (root == null) {
return 0;
} else {
return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;
}
}
/**
* 求二叉树中的节点个数迭代解法O(n)：基本思想同LevelOrderTraversal，
* 即用一个Queue，在Java里面可以用LinkedList来模拟
*/
public static int getNodeNum(TreeNode root) {
if(root == null){
return 0;
}
int count = 1;
Queue queue = new LinkedList();
queue.add(root);
while(!queue.isEmpty()){
TreeNode cur = queue.remove(); // 从队头位置移除
if(cur.left != null){ // 如果有左孩子，加到队尾
queue.add(cur.left);
count++;
}
if(cur.right != null){ // 如果有右孩子，加到队尾
queue.add(cur.right);
count++;
}
}
return count;
}
/**
* 求二叉树的深度（高度） 递归解法： O(n)
* （1）如果二叉树为空，二叉树的深度为0
* （2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1
*/
public static int getDepthRec(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = getDepthRec(root.left);
int rightDepth = getDepthRec(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
/**
* 求二叉树的深度（高度） 迭代解法： O(n)
* 基本思想同LevelOrderTraversal，还是用一个Queue
*/
public static int getDepth(TreeNode root) {
if(root == null){
return 0;
}
int depth = 0; // 深度
int currentLevelNodes = 1; // 当前Level，node的数量
int nextLevelNodes = 0; // 下一层Level，node的数量
LinkedList queue = new LinkedList
();
queue.add(root);
while( !queue.isEmpty() ){
TreeNode cur = queue.remove(); // 从队头位置移除
currentLevelNodes--; // 减少当前Level node的数量
if(cur.left != null){ // 如果有左孩子，加到队尾
queue.add(cur.left);
nextLevelNodes++; // 并增加下一层Level node的数量
}
if(cur.right != null){ // 如果有右孩子，加到队尾
queue.add(cur.right);
nextLevelNodes++;
}
if(currentLevelNodes == 0){ // 说明已经遍历完当前层的所有节点
depth++; // 增加高度
currentLevelNodes = nextLevelNodes; // 初始化下一层的遍历
nextLevelNodes = 0;
}
}
return depth;
}
/**
* 前序遍历，中序遍历，后序遍历 前序遍历递归解法：
* （1）如果二叉树为空，空操作
* （2）如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树
*/
public static void preorderTraversalRec(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preorderTraversalRec(root.left);
preorderTraversalRec(root.right);
}
/**
* 前序遍历迭代解法：用一个辅助stack，总是把右孩子放进栈
* http://www.youtube.com/watch v=uPTCbdHSFg4
*/
public static void preorderTraversal(TreeNode root) {
if(root == null){
return;
}
Stack stack = new Stack(); // 辅助stack
stack.push(root);
while( !stack.isEmpty() ){
TreeNode cur = stack.pop(); // 出栈栈顶元素
System.out.print(cur.val + " ");
// 关键点：要先压入右孩子，再压入左孩子，这样在出栈时会先打印左孩子再打印右孩子
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
}
/**
* 中序遍历递归解法
* （1）如果二叉树为空，空操作。
* （2）如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树
*/
public static void inorderTraversalRec(TreeNode root) {
if (root == null) {
return;
}
inorderTraversalRec(root.left);
System.out.print(root.val + " ");
inorderTraversalRec(root.right);
}
/**
* 中序遍历迭代