目录
1. 层序遍历
2. 判断一棵树是不是完全二叉树
3. 二叉树的构建及遍历
4. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
5. 二叉树搜索树转换成排序双向链表
6. 根据一棵树的前序遍历与中序遍历构造二叉树
7. 根据一棵树的中序遍历与后序遍历构造二叉树
8. 二叉树创建字符串
1. 层序遍历
102. 二叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public List> levelOrder(TreeNode root) {
List> ret = new ArrayList();
if (root == null) return ret;
Queue queue = new linkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
List list = new ArrayList<>(); //存放每一层的数据
while (size > 0) {
TreeNode top = queue.poll();
//System.out.print(top.val+" ");
list.add(top.val);
if (top.left != null) {
queue.offer(top.left);
}
if (top.right != null) {
queue.offer(top.right);
}
size--;
}
ret.add(list);
}
return ret;
}
}
2. 判断一棵树是不是完全二叉树
boolean isCompleteTree(Node root) {
if (root == null) return true;
Queue queue = new linkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node top = queue.poll();
if (top == null) {
break;
}
queue.offer(top.left);
queue.offer(top.right);
}
while (!queue.isEmpty()) {
Node top = queue.peek();
if(top != null) {
return false;
}
queue.poll();
}
return true;
}
3. 二叉树的构建及遍历
二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
import java.util.*;
class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public class Main {
public static int i = 0;
public static TreeNode createTree(String str) {
TreeNode root = null;
if (str.charAt(i) != '#') {
root = new TreeNode(str.charAt(i));
i++;
root.left = createTree(str);
root.right = createTree(str);
} else {
i++;
}
return root;
}
//中序遍历
public static void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.val+" ");
inorder(root.right);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (scan.hasNext()) {
String str = sc.nextLine();
TreeNode root = createTree(str);
inorder(root);
System.out.println();
}
}
}
4. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
236. 二叉树的最近公共祖先 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null; //空树 是没有公共祖先的
if (root == p || root == q) {
return root;
}
TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
if (leftTree != null && rightTree != null) {
return root;
}
if(leftTree == null && rightTree != null) {
return rightTree;
}
if (leftTree != null && rightTree == null) {
return leftTree;
}
if (leftTree == null && rightTree == null) {
return null;
}
return null;
}
}
代码精简版：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遇到null或p或q，直接向上一层返回当前结点
if (root == null | root == p || root == q) return root;
TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
//如果左右两边都有值（不是空），则返回当前结点
if (leftTree != null && rightTree != null) return root;
//不然就是至少有一个是null，返回另一个
return leftTree != null ? leftTree : rightTree;
}
}
5. 二叉树搜索树转换成排序双向链表
二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
public class Solution {
TreeNode prev = null;
public void ConvertChild(TreeNode pCur) {
if (pCur == null) return;
ConvertChild(pCur.left);
pCur.left = prev;
if (prev != null) {
prev.right = pCur;
}
prev = pCur;
ConvertChild(pCur.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) return null;
//调用函数改变结构
ConvertChild(pRootOfTree);
//找头节点
TreeNode head = pRootOfTree;
while(head.left != null) {
head = head.left;
}
return head;
}
}
6. 根据一棵树的前序遍历与中序遍历构造二叉树
105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int preIndex = 0;
public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend) {
if (inbegin > inend) {
return null;
}
TreeNode root = new TreeNode(preorder[preIndex]);
//找到位置
int rootIndex = findInorderIndex(inorder,inbegin,inend,preorder[preIndex]);
preIndex++;
root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
return root;
}
public int findInorderIndex(int[] inorder, int inbegin, int inend,int key) {
for(int i = inbegin; i <= inend; i++) {
if (inorder[i] == key) {
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null) return null;
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
}
7. 根据一棵树的中序遍历与后序遍历构造二叉树
106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int postIndex = 0;
public TreeNode buildTreeChild(int[] inorder, int inbegin, int inend, int[] postorder) {
if (inbegin > inend) return null;
TreeNode root = new TreeNode(postorder[postIndex]);
int rootIndex = findInorderIndex(inorder, inbegin, inend,postorder[postIndex]);
postIndex--;
root.right = buildTreeChild(inorder, rootIndex+1,inend,postorder);
root.left = buildTreeChild(inorder, inbegin,rootIndex-1,postorder);
return root;
}
public int findInorderIndex(int[] inorder, int inbegin, int inend,int key) {
for (int i = inbegin; i <= inend; i++) {
if(inorder[i] == key) {
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder == null || postorder == null) {
return null;
}
postIndex = postorder.length-1;
return buildTreeChild(inorder, 0, inorder.length-1, postorder);
}
}
8. 二叉树创建字符串
606. 根据二叉树创建字符串 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public void tree2strChild(TreeNode t, StringBuilder sb) {
if (t == null) return;
sb.append(t.val);
if (t.left == null) {
if (t.right == null) {
return;
}else {
sb.append("()");
}
} else {
sb.append("(");
tree2strChild(t.left, sb);
sb.append(")");
}
//以上是t的左树部分全部解决完成
if (t.right == null) {
return;
} else {
sb.append("(");
tree2strChild(t.right,sb);
sb.append(")");
}
}
public String tree2str(TreeNode root) {
if (root == null) return null;
StringBuilder sb = new StringBuilder();
tree2strChild(root, sb);
return sb.toString();
}
}
