🍎🍎一、实现二叉树的基本操作
创建一个二叉树，实现二叉树的基本功能。
package com.practice; import java.util.LinkedList; import java.util.Queue; public class BinaryTree { static class TreeNode { public char val; public TreeNode left;//左孩子的引用 public TreeNode right;//右孩子的引用 public TreeNode(char val) { this.val = val; } } /** * 创建一棵二叉树 返回这棵树的根节点 * * @return */ public TreeNode createTree() { TreeNode node1 = new TreeNode('A'); TreeNode node2 = new TreeNode('B'); TreeNode node3 = new TreeNode('C'); TreeNode node4 = new TreeNode('D'); TreeNode node5 = new TreeNode('E'); TreeNode node6 = new TreeNode('F'); TreeNode node7 = new TreeNode('G'); node1.left = node2; node1.right = node3; node2.left = node4; node3.left = node5; node3.right = node6; node4.right = node7; return node1; } // 前序遍历 public void preOrder(TreeNode root) { if (root == null) return; System.out.println(root.val + " "); preOrder(root.left); preOrder(root.right); } // 中序遍历 void inOrder(TreeNode root) { if (root == null) return; inOrder(root.left); System.out.println(root.val + " "); inOrder(root.right); } // 后序遍历 void postOrder(TreeNode root) { if (root == null) return; postOrder(root.left); postOrder(root.right); System.out.println(root.val + " "); } public int nodeSize = 0; /** * 获取树中节点的个数：遍历思路 */ public int size(TreeNode root) { if (root == null) { return 0; } nodeSize++; size(root.left); size(root.right); return nodeSize; } /** * 获取节点的个数：子问题的思路 * * @param root * @return */ int size2(TreeNode root) { if (root == null) { return 0; } return size2(root.left) + size2(root.right) + 1; } /* 获取叶子节点的个数：遍历思路 */ public static int leafSize = 0; int getLeafNodeCount1(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { leafSize++; } getLeafNodeCount1(root.left); getLeafNodeCount1(root.right); return leafSize; } /* 获取叶子节点的个数：子问题 */ int getLeafNodeCount2(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right); } /* 获取第K层节点的个数 */ int getKLevelNodeCount(TreeNode root, int k) { if (root == null) { return 0; } if (k == 1) { return 1; } return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1); } /* 获取二叉树的高度 时间复杂度：O(N) */ int getHeight(TreeNode root) { if(root == null) { return 0; } int leftH = getHeight(root.left); int rightH = getHeight(root.right); return ((leftH>rightH)?leftH:rightH) + 1; } // 检测值为value的元素是否存在 TreeNode find(TreeNode root, char val) { if(root == null) { return null; } if(val == root.val){ return root; } TreeNode leftR = find(root.left,val); if(leftR != null) { return leftR; } TreeNode rightR = find(root.right,val); if(rightR != null) { return rightR; } return null; } //层序遍历 void levelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); if(root != null) { queue.offer(root); } while (!queue.isEmpty()) { TreeNode top = queue.poll(); System.out.print(top.val + " "); if(top.left != null) { queue.offer(top.left); } if(top.right != null) { queue.offer(top.right); } } } // 判断一棵树是不是完全二叉树 boolean isCompleteTree(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); if(root != null) { queue.offer(root); } while (!queue.isEmpty()) { TreeNode cur = queue.poll(); if(cur != null) { queue.offer(cur.left); queue.offer(cur.right); }else { break; } } while (!queue.isEmpty()) { TreeNode cur = queue.poll(); if(cur != null){ return false; } } return true; } }
✨✨二、平衡二叉树的判断
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
class Solution { public boolean isBalanced(TreeNode root) { if(root == null) { return true; } return getHeight2(root) >= 0; } int getHeight2(TreeNode root) { if (root == null) { return 0; } int leftH = getHeight2(root.left); int rightH = getHeight2(root.right); if(leftH >= 0 && rightH >= 0 && Math.abs(leftH - rightH) <= 1) { return Math.max(leftH,rightH) + 1; } else { return -1; } } }
🍎🍎三、二叉树的构建及遍历
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
import java.util.Scanner; class TreeNode { public char value; public TreeNode left; public TreeNode right; public TreeNode(char value) { this.value = value; } } // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case String str = in.nextLine(); TreeNode root = createTree(str); inOrder(root); } } 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.value + " "); inOrder(root.right); } }
🍎🍎四、另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
class Solution { public boolean isSubtree(TreeNode root, TreeNode subRoot) { if(root == null) { return false; } if(isSameTree(root,subRoot)) { return true; } if(isSubtree(root.left,subRoot)) { return true; } if(isSubtree(root.right,subRoot)) { return true; } return false; } public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q != null || p != null && q == null) { return false; } if (p == null && q == null) { return true; } if (p.val != q.val) { return false; } return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } }
✨✨五、对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称
class Solution { public boolean isSymmetric(TreeNode root) { if(root == null){ return true; } return isSymmetricChild(root.left,root.right); } public boolean isSymmetricChild(TreeNode leftTree ,TreeNode righjtTree) { if(leftTree == null && righjtTree != null || leftTree != null && righjtTree == null ) { return false; } if(leftTree == null && righjtTree == null) { return true; } if(leftTree.val != righjtTree.val) { return false; } return isSymmetricChild(leftTree.left,righjtTree.right) && isSymmetricChild(leftTree.right,righjtTree.left); } }
🍎🍎六、检查两棵树是否相同
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if(p == null && q != null || p != null && q == null){ return false; } if(p == null && q == null){ return true; } if(p.val!=q.val){ return false; } return isSameTree(p.left,q.left) &&isSameTree(p.right,q.right); } }
✨✨七、反转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) { return null; } TreeNode tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.left); invertTree(root.right); return root; } }
