- 1.判断一颗树是否是完全二叉树
- 2.二叉树遍历
- 3.从前序与中序遍历序列构造二叉树
- 4.从中序与后续遍历序列构造二叉树
- 5.二叉树的最近公共祖先
- 6.根据二叉树创建字符串
- 7.二叉搜索树与双向链表
1.判断一棵树是否是完全二叉树：
(1)完全二叉树该树中若存在右子树则必然存在左子树
(2)完全二叉树的节点编号必须和满二叉树一一对应(你有的节点必须和满二叉树节点编号相同)。
(3)对于完全二叉树来说一共存在三种节点：
A.度为2的节点有N个
B.度为1的节点最多有一个(恰好就是左树的那个一个节点)
C.度为0的节点有N个
(4)判断方法：
package bin_tree.leetcode;
import java.util.linkedList;
import java.util.Queue;
public class IsCompleteTree {
public boolean isCompleteTree(TreeNode root) {
if (root == null) {
return true;
}
// 层序遍历判断二叉树
Queue queue = new linkedList<>();
queue.offer(root);
// 引入标志位，来区分当前遍历过程处在第一还是第二阶段
boolean isSecondStep = false;
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (!isSecondStep) {
// 此时处在第一阶段
if (cur.left != null && cur.right != null) {
// 当前cur左右子树全部都存在
queue.offer(cur.left);
queue.offer(cur.right);
}else if (cur.left == null && cur.right != null) {
// 此时只有右树没有左树,反例
return false;
}else if (cur.left != null) {
// 只有左树没有右树,此时cur是碰到的第一个只有左树的节点
// 切换状态
isSecondStep = true;
queue.offer(cur.left);
}else {
// 此时左树和右树全部为空，cur第一个碰到的叶子节点
isSecondStep = true;
}
}else {
// 此时处在第二阶段,第二阶段中的所有节点不可能有子树
// 有一个反例就false
if (cur.left != null || cur.right != null) {
return false;
}
}
}
// 遍历全部结束，没有找到反例
return true;
}
}
2.二叉树遍历
2.二叉树遍历
根据题意画出该二叉树的结构：
代码实现:
package bin_tree.NewCoder;
import java.util.Scanner;
// 根据先序遍历结果还原二叉树，输出中序遍历结果
public class KY11 {
private static class TreeNode {
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 获取用户多组输入
while (scanner.hasNext()) {
// 字符串形式的先序二叉树结果
String line = scanner.next();
// str -> TreeNode
TreeNode root = build(line);
// 中序遍历二叉树，按照格式打印结点值
inOrder(root);
// 每个结果占一行
System.out.println();
}
}
private static void inOrder(TreeNode root) {
if (root == null)
return;
inOrder(root.left);
System.out.print(root.val +" ");
inOrder(root.right);
}
// 根据先序遍历结果字符串还原二叉树，返回构建后二叉树的根节点
private static TreeNode build(String line) {
return preOrderBuild(line);
}
// abc##de#g##f###
// str -> char
// 当前处理到哪个字符了
static int index = 0;
private static TreeNode preOrderBuild(String line) {
char c = line.charAt(index);
if (c == '#') {
return null;
}
TreeNode root = new TreeNode(c);
index ++;
root.left = preOrderBuild(line);
index ++;
root.right = preOrderBuild(line);
return root;
}
}
运行截图：
3.从二叉树与中序遍历序列构造二叉树
1.代码实现：
package bin_tree.leetcode;
public class Num105 {
// 当前处理到前序遍历的哪个位置
int index = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeInternal(preorder,inorder,0,inorder.length);
}
public TreeNode buildTreeInternal(int[] preOrder,int[] inOrder,int left,int right) {
if(left >= right) {
return null;
}
if (index >= preOrder.length) {
return null;
}
TreeNode root = new TreeNode(preOrder[index]);
index ++;
int pos = find(inOrder,left,right,root.val);
root.left = buildTreeInternal(preOrder,inOrder,left,pos);
root.right = buildTreeInternal(preOrder,inOrder,pos + 1,right);
return root;
}
private int find(int[] inOrder, int left, int right, int val) {
for (int i = left; i < right; i++) {
if (inOrder[i] == val) {
return i;
}
}
return -1;
}
}
4.从中序与后续遍历序列构造二叉树
4.从中序与后续遍历序列构造二叉树
package bin_tree.leetcode;
import java.util.HashMap;
import java.util.Map;
public class Num106 {
// 存储中序遍历的对应的值和索引
Map map = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
// 将后序遍历结果反转
int[] preOrder = reverse(inorder,postorder);
return buildTreeInternal(preOrder,inorder,0,inorder.length);
}
int index = 0;
public TreeNode buildTreeInternal(int[] preOrder,int[] inOrder,int left,int right) {
if(left >= right) {
return null;
}
if (index >= preOrder.length) {
return null;
}
TreeNode root = new TreeNode(preOrder[index]);
index ++;
int pos = map.get(root.val);
root.right = buildTreeInternal(preOrder,inOrder,pos + 1,right);
root.left = buildTreeInternal(preOrder,inOrder,left,pos);
return root;
}
private int[] reverse(int[] inorder,int[] postorder) {
int[] ret = new int[postorder.length];
for (int i = 0; i < ret.length; i++) {
ret[i] = postorder[ret.length - 1 - i];
}
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i],i);
}
return ret;
}
}
5.二叉树的最近公共祖先
5.二叉树的最近公共祖先
package bin_tree.leetcode;
public class Num236 {
TreeNode lca;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
// 从根节点出发进行后序遍历，找到lca(p和q出现在三个位置的两个)
find(root,p,q);
return lca;
}
// 在以root为根节点的二叉树中，是否能同时找到p和q
private boolean find(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return false;
}
int left = find(root.left,p,q) ? 1 : 0;
int right = find(root.right,p,q) ? 1 : 0;
int mid = (root == p || root == q) ? 1 : 0;
if (left + right + mid == 2) {
lca = root;
return true;
}
return (left + right + mid) > 0;
}
}
6.根据二叉树创建字符串
6.根据二叉树创建字符串
package bin_tree.leetcode;
public class Num606 {
StringBuilder sb = new StringBuilder();
// "1(2(4))(3)"
public String tree2str(TreeNode root) {
if (root == null) {
return "";
}
preOrder(root);
return sb.toString();
}
private void preOrder(TreeNode root) {
if (root == null) {
return;
}
// "1(2(4))(3)"
sb.append(root.val);
if (root.left != null) {
sb.append("(");
// 先序遍历左树
preOrder(root.left);
sb.append(")");
}else {
// 左空，判断右树是否为空
if (root.right != null) {
sb.append("()");
}
}
if (root.right != null) {
sb.append("(");
preOrder(root.right);
sb.append(")");
}
}
}
7.二叉搜索树与双向链表
package bin_tree.NewCoder;
import bin_tree.leetcode.TreeNode;
public class ConvertTree2linkedList {
// 传入一个BST的根节点，就可以将其转为双向链表，且返回链表头
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null ||(pRootOfTree.left == null &&
pRootOfTree.right == null)) {
return pRootOfTree;
}
TreeNode left = Convert(pRootOfTree.left);
TreeNode leftTail = left;
while (leftTail != null && leftTail.right != null) {
leftTail = leftTail.right;
}
if (leftTail != null) {
leftTail.right = pRootOfTree;
pRootOfTree.left = leftTail;
}
TreeNode right = Convert(pRootOfTree.right);
if (right != null) {
right.left = pRootOfTree;
pRootOfTree.right = right;
}
return left == null ? pRootOfTree : left;
}
}
