目录
1.树的结构
1.1树结构概念
2.二叉树(重点)
2.1概念
2.2常见的二叉树
2.3二叉树的遍历问题
2.4二叉树的基本操作
2.5二叉树的基础面试题
1.树的结构
1.1树结构概念
树是一种非线性的数据结构,它是由n(n>=0)个有限节点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树,也就是说它是根朝上,而叶子朝下的。树天然具有高效的查找与搜索语义!
为什么会存在树结构?
1.2关于树的基础概念
2.二叉树(重点)
2.1概念
一颗二叉树是节点的一个有限集合,该集合或者为空,或者是由一个根节点加上两颗别称为左子树和右子树的二叉树组成。通俗来讲,就是树中节点最大的度为2。
二叉树的常用性质:
2.2常见的二叉树
满二叉树与完全二叉树:
2.3二叉树的遍历问题
所有二叉树的基础操作,其实所有二叉树的问题的解决思路都是遍历问题的衍生!
遍历:按照一定的顺序访问这个集合的所有元素,做到不遗漏,不重复!
前序遍历:根左右
public void preOrder(TreeNode root){
if (root == null){
return;
}
//先输出根节点
System.out.print(root.val + " ");
//左子树的输出交给子函数
preOrder(root.left);
//右子树的输出交给子函数
preOrder(root.right);
}
中序遍历:左根右
public void inOrder(TreeNode root){
if (root == null){
return;
}
//左子树交给子函数处理
inOrder(root.left);
//输出根节点
System.out.print(root.val + " ");
//右子树交给子函数处理
inOrder(root.right);
}
后序遍历:左右根
public void postOrder(TreeNode root){
if (root == null){
return;
}
//左子树交给子函数出库
postOrder(root.left);
//右子树交给子函数处理
postOrder(root.right);
//输出根节点
System.out.print(root.val + " ");
}
层序遍历:
2.4二叉树的基本操作
package bintree;
//二叉树的结点
class TreeNode{
//当前节点的值
E val;
//左子树的根
TreeNode left;
//右子树的根
TreeNode right;
public TreeNode(E val) {
this.val = val;
}
}
public class MyBinTree {
public TreeNode root;
//建立二叉树
public void build(){
TreeNode node = new TreeNode<>('A');
TreeNode node1 = new TreeNode<>('B');
TreeNode node2 = new TreeNode<>('C');
TreeNode node3 = new TreeNode<>('D');
TreeNode node4 = new TreeNode<>('E');
TreeNode node5 = new TreeNode<>('F');
TreeNode node6 = new TreeNode<>('G');
TreeNode node7 = new TreeNode<>('H');
root = node;
node.left = node1;
node.right = node2;
node1.left = node3;
node1.right = node4;
node4.left = node6;
node6.right = node7;
node2.right = node5;
}
public void preOrder(TreeNode root){
if (root == null){
return;
}
//先输出根节点
System.out.print(root.val + " ");
//左子树的输出交给子函数
preOrder(root.left);
//右子树的输出交给子函数
preOrder(root.right);
}
public void inOrder(TreeNode root){
if (root == null){
return;
}
//左子树交给子函数处理
inOrder(root.left);
//输出根节点
System.out.print(root.val + " ");
//右子树交给子函数处理
inOrder(root.right);
}
public void postOrder(TreeNode root){
if (root == null){
return;
}
//左子树交给子函数出库
postOrder(root.left);
//右子树交给子函数处理
postOrder(root.right);
//输出根节点
System.out.print(root.val + " ");
}
public int getNodes(TreeNode root){
if (root == null){
return 0;
}
return 1 + getNodes(root.left) + getNodes(root.right);
}
public int getLeafNodes(TreeNode root){
if(root == null){
return 0;
}
if (root.left == null && root.right == null){
return 1;
}
return getLeafNodes(root.left) + getLeafNodes(root.right);
}
public int getKLevelNodes(TreeNode root,int k){
if (root == null || k <= 0){
return 0;
}
if (k == 1){
return 1;
}
return getKLevelNodes(root.left,k - 1) +getKLevelNodes(root.right,k - 1);
}
public boolean contains(TreeNode root,E val){
if (root == null){
return false;
}
if (root.val.equals(val)){
return true;
}
return contains(root.left,val) || contains(root.right,val);
}
}
2.5二叉树的基础面试题
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
// 边界
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null) {
return false;
}
// 恰好root和subRoot就是相同的树 => true
return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}
public boolean isSameTree(TreeNode p, TreeNode q) {
// 1.边界
if (p == null && q == null) {
// 都是空树,就认为相同
return true;
}
if (p == null || q == null) {
// 有一棵树为空,另一棵树不为空
return false;
}
// p和q都不为空,判断一下节点值。子树的判断交给子函数
return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
// 求左树高度
int left = height(root.left);
// 求右树高度
int right = height(root.right);
int abs = Math.abs(left - right);
return abs <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
public int height(TreeNode root) {
return root == null ? 0 : 1 + Math.max(height(root.left),height(root.right));
}
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Deque queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode t1 = queue.poll();
TreeNode t2 = queue.poll();
if (t1 == null && t2 == null) {
continue;
}
if (t1 == null || t2 == null) {
// 找到反例
return false;
}
if (t1.val != t2.val) {
// 找到反例
return false;
}
// 继续t1.left t2.right入队
queue.offer(t1.left);
queue.offer(t2.right);
// 继续t1.right t2.left
queue.offer(t1.right);
queue.offer(t2.left);
}
return true;
}
public boolean isCompleteTree(TreeNode root) {
Deque 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) {
queue.offer(cur.left);
queue.offer(cur.right);
}else if (cur.left != null) {
// 此时只有左树没有右树,转阶段
isSecondStep = true;
queue.offer(cur.left);
}else if (cur.right != null) {
// 只有右树没左树,反例
return false;
}else {
// 碰到叶子结点,转阶段
isSecondStep = true;
}
}else {
// 此时处在第二阶段,所有节点都必须为叶子结点。
if (cur.left != null || cur.right != null) {
// 不是叶子结点,反例
return false;
}
}
}
return true;
}
public ListpreorderTraversal(TreeNode root) { List ret = new ArrayList<>(); if (root == null) { return ret; } Deque stack = new LinkedList<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); ret.add(cur.val); if (cur.right != null) { stack.push(cur.right); } if (cur.left != null) { stack.push(cur.left); } } return ret; }
public ListinorderTraversal(TreeNode root) { List ret = new ArrayList<>(); if (root == null) { return ret; } Deque stack = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { // 先一路向左走到底 while (cur != null) { stack.push(cur); cur = cur.left; } // cur已经为空,弹出栈顶元素,就是第一个左子树为空的结点 cur = stack.pop(); ret.add(cur.val); // 继续访问右子树 cur = cur.right; } return ret; }
public ListpostorderTraversal(TreeNode root) { List ret = new ArrayList<>(); if (root == null) { return ret; } TreeNode cur = root; Deque stack = new ArrayDeque<>(); // 上一个完全处理完毕的节点. TreeNode prev = null; while (cur != null || ! stack.isEmpty()) { // 1.先一路向左走到底 while (cur != null) { stack.push(cur); cur = cur.left; } // 2.查看当前栈顶元素的情况 cur = stack.pop(); // 检查右子树的情况 if (cur.right == null || cur.right == prev) { // 此时右子树为空或者右子树已经被处理完毕 // 此时可以放心访问cur节点-根 ret.add(cur.val); // cur节点就是最新的处理结束的结点 prev = cur; // 继续从栈中取出栈顶元素 cur = null; }else { // 此时cur.right != null 且没被访问过,继续访问右子树 stack.push(cur); // 继续访问右子树 cur = cur.right; } } return ret; }
// 最近公共祖先
private TreeNode lca;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 从树中每个节点开始遍历找p和q这两个节点
findNode(root,p,q);
return lca;
}
private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return false;
}
// 返回1说明,此时从左子树中至少找到了一个节点
int left = findNode(root.left,p,q) ? 1 : 0;
// 返回1说明在右子树中也至少找到了节点
int right = findNode(root.right,p,q) ? 1 : 0;
// 当前树根就是p或者q的其中一个
int mid = (root == p || root == q) ? 1 : 0;
if (left + right + mid == 2) {
// 此时p和q出现在以root为根的两个位置,这个root一定是lca!!!
lca = root;
}
// 大于0,说明至少找到一个节点
return (left + right + mid) > 0;
}
import java.util.*
// 节点类定义
class TreeNode {
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public class Main{
// 表示当前处理到先序遍历的哪个字符了
private static int index = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
// 从外部获取了一个先序遍历的结果集字符串
// abc##de#g##f###
String str = scanner.nextLine();
// 就按照先序遍历的方式还原这个二叉树,返回根节点
TreeNode root = preOrderBuild(str);
// 按照中序遍历的方式输出二叉树的节点值
inOrder(root);
System.out.println();
index = 0;
}
}
private static void inOrder(TreeNode root) {
if (root == null) {
return;
}
// 先递归左子树
inOrder(root.left);
// 根
System.out.print(root.val + " ");
// 最后递归访问右子树
inOrder(root.right);
}
private static TreeNode preOrderBuild(String str) {
// 读取一个字符
// abc##de#g##f###
char cur = str.charAt(index);
if (cur == '#') {
// 空树,无需创建节点
return null;
}
TreeNode root = new TreeNode(cur);
index ++;
root.left = preOrderBuild(str);
index ++;
root.right = preOrderBuild(str);
return root;
}
}
// 表示当前处理到前序遍历的哪个元素
private int index = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeHelper(preorder,inorder,0,inorder.length - 1);
}
private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
// 边界
if (left > right) {
// [2,1) => 空区间
return null;
}
if (index == preorder.length) {
// 前序遍历的元素已经处理完毕,没有新节点
return null;
}
// 从前序遍历中取出当前树的树根节点
TreeNode root = new TreeNode(preorder[index]);
index ++;
int pos = find(root.val,inorder);
root.left = buildTreeHelper(preorder,inorder,left,pos - 1);
root.right = buildTreeHelper(preorder,inorder,pos + 1,right);
return root;
}
private int find(int val, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == val) {
return i;
}
}
return -1;
}



