8.二叉树的一系列问题
1.二叉树的前中后序遍历(非递归)
先序遍历,用一个栈来保存, 挺简单的.
// 中 - 左 - 右
public static void preOrder(Node root){
if (root != null){
Stack<Node> stack = new Stack<>();
stack.add(root);
Node curr = null;
while (!stack.isEmpty()){
curr = stack.pop();
System.out.println(curr.value);
if( curr.right != null )
stack.push(curr.right);
if( curr.left != null )
stack.push(curr.left);
}
}
}
中序遍历,应该是三种遍历中比较难理解的. 树往左下部分走,全部压入栈中.
// 左 - 中 - 右
public static void inOrder(Node root){
if (root != null){
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() || root != null){
if( root != null ){
stack.push(root);
root = root.left;
}
else {
root = stack.pop();
System.out.println(root.value);
root = root.right;
}
}
}
}
后续遍历可以通过先序遍历理解. 先序遍历是中-左-右,它很容易改为中-右-左的实现方式. 再借助一个栈就变为左-右-中的形式了.
// 左 - 右 - 中
/*
前面的先序遍历是:中左右, 将它改成中右左. 然后用一个栈调成左右中即可
*/
public static void posOrder(Node root){
if( root != null ){
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.push(root);
Node curr = null;
while (!stack1.isEmpty()){
curr = stack1.pop();
stack2.push(curr);
if ( curr.left != null )
stack1.push(curr.left);
if( curr.right != null )
stack1.push(curr.right);
}
while (!stack2.isEmpty()){
System.out.println(stack2.pop());
}
}
}
2.在二叉树中找一个节点的后继节点
题目:现有一种新的二叉树节点类型的定义如下
public static class Node{
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int data){
this.value = data;
}
}
在二叉树的中序遍历的序列中， node的下一个节点叫做node的后继节点。 该结构比普通二叉树节点结构多了一个指向父节点的parent指针。假设有一 棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向 自己的父节点，头节点的parent指向null。只给一个在二叉树中的某个节点 node，请实现返回node的后继节点的函数。
/*
找后继节点:
1. 如果有右子树,就是右子树中最左边的节点.
2. 如果无右子树,就向上找,当前节点是父节点的左孩子.
*/
/*
找前驱节点:
1. 如果有左子树,就是左子树的醉右边的节点.
2. 如果无左子树,就向上找,当前节点是父节点的右孩子.
*/
public static Node getSuccessorNode(Node node){
if (node == null)
return node;
// 如果有右子树, 就返回右子树中最左边的节点,
if (node.right != null)
return getLeftMost(node);
// 如果没有右子树, 就返回
else {
Node parent = node.parent;
// 当节点node是父节点parent的左孩子时停, 否则一直向上找.
while (parent != null && parent.left != node) {
node = parent;
parent = node.parent;
}
return parent;
}
}
// 返回树种最左边的节点.
private static Node getLeftMost(Node node){
if (node == null)
return node;
while (node.left != null)
node = node.left;
return node;
}
3.二叉树的序列化与反序列化
序列化:将存在内存中的数据结构,以某种形式存在文件磁盘中,
反序列化:并且能根据这个文件回推出原先的数据结构.
以先序遍历为例:如果是null就用#代替, 节点与节点间用_分隔.
/*
以先序遍历为例:如果是null就用#代替, 节点与节点间用_分隔.
*/
public static String serialByPre(Node node){
if (node == null)
return "#_";
String res = node.value+"_";
res += serialByPre(node.left);
res += serialByPre(node.right);
return res;
}
/*
反序列化过程:
*/
public static Node reconByPreString(String preStr){
String[] values = preStr.split("_");
Queue<String> queue = new LinkedList<>();
for (int i = 0; i < values.length ; i++) {
queue.offer(values[i]);
}
return reconPreOrder(queue);
}
// 建立二叉树
public static Node reconPreOrder(Queue<String> queue){
String value = queue.poll();
if( value.equals("_"))
return null;
Node head = new Node( Integer.valueOf(value) );
head.left = reconPreOrder(queue);
head.right = reconPreOrder(queue);
return head;
}
我们的OJ的后台对比答案的时候是应用了序列化. 将你上传的答案序列化后,与后台的答案进行比较即可.
4.判断二叉树是否是平衡二叉树
递归函数的设计,需要
-
左子树是否平衡二叉树 -
右子树是否是平衡二叉树 -
左右子树的高度, 然后判断左右子树的高度是否大于1.
所以设计的递归函数返回时需要得到两个值,一个是此树是否是平衡二叉树,以及高度.
public static class ReturnData {
boolean isBalance;
int height;
ReturnData(boolean isBalance, int height ){
this.isBalance = isBalance;
this.height = height;
}
}
public static ReturnData process(Node root){
if (root == null)
return new ReturnData(true, 0);
ReturnData leftData = process(root.left);
if (leftData.isBalance == false)
return new ReturnData(false, 0);
ReturnData rightDta = process(root.right);
if (rightDta.isBalance == false)
return new ReturnData(false, 0);
if( Math.abs(leftData.height - rightDta.height) > 1)
return new ReturnData(false, 0);
return new ReturnData(true, Math.max(leftData.height, rightDta.height) + 1);
}
所以说,只要是处理树的问题一定要先想到用递归的方式. 递归的话,就需要找好需要的条件.
5.判断二叉树是否是二叉搜索树
二叉树的中序遍历是升序的就是二叉搜索树.从这个角度来看就是比较简单的了.写出二叉树的先序遍历就完成了.
public static boolean isBST(Node root){
int pre = Integer.MIN_VALUE;
if (root != null){
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() || root != null){
if (root != null){
stack.push(root);
root = root.left;
}
else {
root = stack.pop();
// 比较
if (root.value < pre)
return false;
pre = root.value;
root = root.right;
}
}
}
return true;
}
6.判断二叉树是否是完全二叉树
判断逻辑是,二叉树按照层遍历.
-
如果一个节点有右孩子但是没左孩子, 它不是完全二叉树. -
如果一个节点有左孩子无右孩子,或者既无左孩子也无右孩子, 那么它后面出现的节点必须是叶节点.
/*
存在两个情况:
1. 节点有右孩子,无左孩子,直接返回false
2. 节点有左孩子无右孩子,或者节点既无右孩子也无左孩子. 这时后面的节点必须全为叶节点, 开启leaf = true模式.
*/
public static boolean isCBT(Node root){
if (root == null)
return true;
Queue<Node> queue = new LinkedList<>();
boolean leaf = false;
Node left = null;
Node right = null;
Node curr = null;
queue.offer(root);
while ( !queue.isEmpty() ){
curr = queue.poll();
left = curr.left;
right = curr.right;
/*
(leaf && (left != null || right != null)) : 表示情况2后面的节点有不是叶节点的
(left == null && right != null): 就是情况1
*/
if( (leaf && (left != null || right != null)) || (left == null && right != null) ){
return false;
}
if( left != null ){
queue.offer(left);
}
if( right != null ){
queue.offer(right);
}
// 节点有左孩子无右孩子,或者节点既无右孩子也无左孩子. 开启leaf.
if (left == null || right == null){
leaf = true;
}
}
return false;
}
7. 一个完全二叉树,求节点的个数
要求时间复杂度低于O(n). 我们知道一颗满二叉树节点的个数等于 . 所以我们可以利用这个性质降低代码的时间复杂度.
第一种情况如下图所示,, 那么节点个数 = + 递归右子树.第二种情况如下图所示, 若右子树的最深深度不等于数的深度,那么节点个数 = + 递归左子树.
public static int nodeNum(Node node){
if (node == null)
return 0;
return bs(node, 1, mostLeftLevel(node, 1));
}
/*
node:当前节点 level:当前节点在第几层 h:树的高度
return: 以这个节点的一共有多少个节点
*/
private static int bs(Node node, int level, int h){
if( level == h )
return 1;
// 1. 若右子树的最深深度等于数的深度
if( mostLeftLevel(node.right, level + 1) == h ){
return (int)(Math.pow(2, h - level) + bs(node.right, level + 1, h ));
}
// 2. 若右子树的最深深度不等于数的深度
else {
return (int)(Math.pow(2,h - level - 1) + bs(node.left, level + 1, h));
}
}
// 求树的高度
private static int mostLeftLevel(Node node, int level){
while (node.left != null){
level++;
node = node.left;
}
return level;
}