首页 / 算法 / 数据结构树及相关算法题
数据结构树及相关算法题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构树及相关算法题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含16148字，纯文字阅读大概需要24分钟。
内容图文
树
定义
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
有一个特殊的结点叫根节点，根节点没有 前驱节点。
除根节点外，其余节点被分为M（M>0）个互不相交的集合T1，T2…Tm，其中每一个集合Ti(1<=i<=m)有是一颗与树类似的子树，每颗子树的根节点有且只有一个前驱，可以有0个或者多个后继。
树是递归定义的。
重要概念
节点的度：一个节点含有的子树的个数称为该节点的度
树的度：一棵树中，最大的节点的度称为树的度
叶子节点或终端节点：度为0的节点称为叶节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点
根结点：一棵树中，没有双亲结点的结点
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
树的高度或深度：树中节点的最大层次
非终端节点或分支节点：度不为0的节点
兄弟节点：具有相同父节点的节点互称为兄弟节点
堂兄弟节点：双亲在同一层的节点互为堂兄弟
节点的祖先：从根到该节点所经分支上的所有节点
子孙：以某节点为根的子树中任一节点都称为该节点的子孙
森林：由m（m>=0）棵互不相交的树的集合称为森林
树的表示形式
树有多种表示方式：双亲表示法、孩子表示法、孩子兄弟表示法等。
孩子兄弟表示法：
class Node{
int value; //树中存储的数据
Node firstChild;//第一个孩子引用
Node nextBrother;//下一个兄弟引用
}
二叉树
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点：
每个结点最多有两棵子树，即二叉树不存在度大于 2 的结点
二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树
二叉树的基本形态
从左往右依次是：空树、只有根节点的二叉树、节点只有左子树、节点只有右子树、节点的左右子树均存在，一般二叉树都是由上述基本形态结合而形成的。
满二叉树
满二叉树: 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是
2
k
?
1
2^k-1
2k?1 ，则它就是满二叉树。
完全二叉树
完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
二叉树的性质
若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有
2
i
?
1
2^{i-1}
2i?1(i>0)个结点
若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是
2
k
?
1
2^k-1
2k?1(k>=0)
二叉树的基础面试题
- 二叉树的前序遍历题目链接
前中后序的二叉树遍历采用递归的方式来写有一个模板，只需要改变几行代码的顺序就好。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
import java.util.LinkedList;
import java.util.List;
class Solution {
static List<Integer> list = new LinkedList();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null){
return new ArrayList<>();
}
List<Integer> left = preorderTraversal(root.left);
List<Integer> right = preorderTraversal(root.right);
List<Integer> list = new ArrayList<>();
list.add(root.val);
list.addAll(left);
list.addAll(right);
return list;
}
}
方法二：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> result;
public void traversalNode(TreeNode node) {
if(node != null) {
result.add(node.val);
if(node.left != null) traversalNode(node.left);
if(node.right != null) traversalNode(node.right);
}
return;
}
public List<Integer> preorderTraversal(TreeNode root) {
result = new ArrayList<Integer>();
traversalNode(root);
return result;
}
}
- 二叉树的中序遍历题目链接
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null){
return new ArrayList<>();
}
List<Integer> left = inorderTraversal(root.left);
List<Integer> right = inorderTraversal(root.right);
List<Integer> list = new ArrayList<>();
list.addAll(left);
list.add(root.val);
list.addAll(right);
return list;
}
}
- 二叉树的后序遍历题目链接
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null){
return new ArrayList<>();
}
List<Integer> left = postorderTraversal(root.left);
List<Integer> right = postorderTraversal(root.right);
List<Integer> list = new ArrayList<>();
list.addAll(left);
list.addAll(right);
list.add(root.val);
return list;
}
}
- 检查两棵树是否相同题目链接
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null){
return true;
}else if(p == null || q == null){
return false;
}else if(p.val != q.val){
return false;
}else{
return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
}
方法二：
public static boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val
&& isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}
- 另一棵树的子树题目链接
class Solution {
public static boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val
&& isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) {
return false;
}
if (isSameTree(s, t)) {
return true;
}
if (isSubtree(s.left, t)) {
return true;
}
return isSubtree(s.right, t);
}
}
- 二叉树最大深度题目链接
class Solution {
public static int maxDepth(TreeNode root){
if (root == null){
//根不存在
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left,right)+1;
}
}
class Solution {
public static int maxDepth(TreeNode root){
if (root == null) {
return 0;
}
return Integer.max(maxDepth(root.left),maxDepth(root.right)) + 1;
}
}
- 判断一颗二叉树是否是平衡二叉树题目链接
class Solution {
public static int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
return Integer.max(getHeight(root.left), getHeight(root.right)) + 1;
}
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
boolean isLeftBalance = isBalanced(root.left);
if (!isLeftBalance) {
return false;
}
boolean isRightBalance = isBalanced(root.right);
if (!isRightBalance) {
return false;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
int diff = leftHeight - rightHeight;
return diff >= -1 && diff <= 1;
}
}
- 对称二叉树 题目链接
class Solution {
private static boolean isMirror(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val
&& isMirror(p.left, q.right)
&& isMirror(p.right, q.left);
}
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isMirror(root.left, root.right);
}
}
二叉树的进阶面试题
- 二叉树的构建及遍历题目链接
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main {
static class TreeNode {
char val;
TreeNode left;
TreeNode right;
public TreeNode(char rootValue) {
this.val = rootValue;
}
@Override
public String toString() {
return "TreeNode{" +
"val=" + val +
'}';
}
}
private static int index;
private static TreeNode buildTree3(char[] preorder) {
if (index >= preorder.length) {
return null;
}
char rootValue = preorder[index++];
if ( rootValue == '#') {
return null;
}
TreeNode root = new TreeNode(rootValue);
root.left = buildTree3(preorder);
root.right = buildTree3(preorder);
return root;
}
private static TreeNode buildTree2(List<Character> preorder) {
if (preorder.isEmpty()) {
return null;
}
char rootValue = preorder.remove(0);
if (rootValue == '#') {
return null;
}
TreeNode root = new TreeNode(rootValue);
root.left = buildTree2(preorder);
root.right = buildTree2(preorder);
return root;
}
static class ReturnType {
TreeNode builtRoot;
int used;
}
private static ReturnType buildTree(List<Character> preorder) {
if (preorder.isEmpty()) {
ReturnType rt = new ReturnType();
rt.builtRoot = null;
rt.used = 0;
return rt;
}
// 1. 获取根的值
char rootValue = preorder.get(0);
if (rootValue == '#') {
ReturnType rt = new ReturnType();
rt.builtRoot = null;
rt.used = 1;
return rt;
}
TreeNode root = new TreeNode(rootValue);
// 2. 构建左子树
List<Character> leftSubTreePreorder = preorder.subList(1, preorder.size());
ReturnType leftReturn = buildTree(leftSubTreePreorder);
root.left = leftReturn.builtRoot;
// 3. 构建右子树
List<Character> rightSubTreePreorder = preorder.subList(1 + leftReturn.used, preorder.size());
ReturnType rightReturn = buildTree(rightSubTreePreorder);
root.right = rightReturn.builtRoot;
// 4. 返回我们的两个信息
ReturnType rt = new ReturnType();
rt.builtRoot = root;
rt.used = 1 + leftReturn.used + rightReturn.used;
return rt;
}
private 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 scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
String s = scanner.nextLine();
char[] chars = s.toCharArray();
index = 0;
TreeNode root = buildTree3(chars);
inorder(root);
System.out.println();
}
}
}
- 二叉树的分层遍历题目链接
public static void levelOrder(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> levelQueue = new LinkedList<>();
queue.add(root);
levelQueue.add(0);
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
int level = levelQueue.remove();
System.out.println(level + ": " + node.val);
if (node.left != null) {
queue.add(node.left);
levelQueue.add(level + 1);
}
if (node.right != null) {
queue.add(node.right);
levelQueue.add(level + 1);
}
}
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if (root == null) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> levelQueue = new LinkedList<>();
queue.add(root);
levelQueue.add(0);
int lastLevel = -1;
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
int level = levelQueue.remove();
if (lastLevel != level){
list.add(new ArrayList<>());
}
lastLevel = level;
List<Integer> rowList = list.get(level);
rowList.add(node.val);
if (node.left != null) {
queue.add(node.left);
levelQueue.add(level + 1);
}
if (node.right != null) {
queue.add(node.right);
levelQueue.add(level + 1);
}
}
return list;
}
- 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先题目链接
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p == root || q == root) {
return root;
}
boolean pInLeft = containsNode(root.left, p);
boolean qInLeft = containsNode(root.left, q);
if (pInLeft && !qInLeft) {
return root;
}
if (!pInLeft && qInLeft) {
return root;
}
if (pInLeft) {
return lowestCommonAncestor(root.left, p, q);
} else {
return lowestCommonAncestor(root.right, p, q);
}
}
private static boolean containsNode(TreeNode root, TreeNode p) {
if (root == null) {
return false;
}
if (root == p) {
return true;
}
if (containsNode(root.left, p)) {
return true;
}
return containsNode(root.right, p);
}
}
- 二叉树搜索树转换成排序双向链表题目链接
import java.util.ArrayList;
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree==null)
return null;
ArrayList<TreeNode> list=new ArrayList<>();
Convert(list,pRootOfTree);
return Convert(list);
}
public void Convert(ArrayList<TreeNode>list,TreeNode root){
if (root!=null){
Convert(list,root.left);
list.add(root);
Convert(list,root.right);
}
}
public TreeNode Convert(ArrayList<TreeNode> list){
TreeNode head=list.get(0);
TreeNode cur=head;
for (int i=1;i<list.size();++i){
TreeNode node=list.get(i);
node.left=cur;
cur.right=node;
cur=node;
}
return head;
}
}
- 根据一棵树的前序遍历与中序遍历构造二叉树题目链接
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) {
return null;
}
int rootValue = preorder[0];
TreeNode root = new TreeNode(rootValue);
int leftSize = 0;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == rootValue) {
leftSize = i;
}
}
int[] leftPreorder = Arrays.copyOfRange(preorder, 1, 1 + leftSize);
int[] leftInorder = Arrays.copyOfRange(inorder, 0, leftSize);
root.left = buildTree(leftPreorder, leftInorder);
int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + leftSize, preorder.length);
int[] rightInorder = Arrays.copyOfRange(inorder, leftSize + 1, inorder.length);
root.right = buildTree(rightPreorder, rightInorder);
return root;
}
- 从中序和后序序列构建二叉树题目链接
public TreeNode buildTree(int[] inorder, int[] postorder) {
if( inorder.length == 0 && postorder.length == 0){
return null;
}
int rootValue = postorder[postorder.length - 1];
TreeNode root = new TreeNode(rootValue);
int leftSize = 0;
for(int i = 0 ;i < inorder.length;i++){
if(inorder[i] == rootValue){
leftSize = i;
}
}
int []leftInorder = Arrays.copyOfRange(inorder,0,leftSize);
int []leftPostOrder = Arrays.copyOfRange(postorder,0,leftSize);
root.left = buildTree1(leftInorder,leftPostOrder);
int []rightInorder = Arrays.copyOfRange(inorder,1+leftSize,inorder.length);
int []rightPostOrder = Arrays.copyOfRange(postorder,leftSize,postorder.length-1);
root.right = buildTree1(rightInorder,rightPostOrder);
return root;
}
- 根据二叉树创建字符串题目链接
class Solution {
private StringBuilder sb;
private void preorder(TreeNode root) {
if (root == null) {
sb.append("()");
return;
}
sb.append("(");
sb.append(root.val);
if(root.left == null && root.right == null){
}
else if(root.right == null){
preorder(root.left);
}else{
preorder(root.left);
preorder(root.right);
}
sb.append(")");
}
public String tree2str(TreeNode t) {
sb = new StringBuilder();
preorder(t);
sb.delete(0, 1);
sb.delete(sb.length() - 1, sb.length());
return sb.toString();
}
}
前中后序的非递归遍历
由于递归遍历会不断调用栈，时间复杂度高
前序遍历
public static void preorder(TreeNode root) {
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
System.out.println(cur.val);
stack.push(cur);
cur = cur.left;
}
TreeNode pop = stack.pop();
cur = pop.right;
}
}
中序遍历
public static void inorder(TreeNode root) {
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode pop = stack.pop();
System.out.println(pop.val);
cur = pop.right;
}
}
后序遍历
public static void postorder(TreeNode root) {
TreeNode cur = root;
TreeNode last = null; // 记录上次刚刚后序遍历过的结点
Stack<TreeNode> stack = new Stack<>();
//int height = -1;
List<TreeNode> pathOf8 = null;
List<TreeNode> pathOf4 = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
// 第一次经过结点
stack.push(cur);
cur = cur.left;
}
TreeNode pop = stack.peek();
//height = Integer.max(height, stack.size());
if (pop.right == null) {
if (pop.val == 4) {
pathOf4 = new ArrayList<>(stack);
} else if (pop.val == 8) {
pathOf8 = new ArrayList<>(stack);
}
// 第二次经过结点，但同时看作第三次经过结点
stack.pop();
//System.out.println(pop.val);
last = pop;
} else if (pop.right == last) {
if (pop.val == 4) {
pathOf4 = new ArrayList<>(stack);
} else if (pop.val == 8) {
pathOf8 = new ArrayList<>(stack);
}
// 第三次经过结点
stack.pop();
//System.out.println(pop.val);
last = pop;
} else {
// 第二次经过结点
cur = pop.right;
}
}
//System.out.println(height);
System.out.println(pathOf4);
System.out.println(pathOf8);
}
验证demo:
import java.util.Arrays;
public class TestDemo {
public static TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) {
return null;
}
int rootValue = preorder[0];
TreeNode root = new TreeNode(rootValue);
int leftSize = 0;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == rootValue) {
leftSize = i;
}
}
int[] leftPreorder = Arrays.copyOfRange(preorder, 1, 1 + leftSize);
int[] leftInorder = Arrays.copyOfRange(inorder, 0, leftSize);
root.left = buildTree(leftPreorder, leftInorder);
int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + leftSize, preorder.length);
int[] rightInorder = Arrays.copyOfRange(inorder, leftSize + 1, inorder.length);
root.right = buildTree(rightPreorder, rightInorder);
return root;
}
public static void main(String[] args) {
int[] preorder = {1, 2, 4, 5, 8, 3, 6, 7};
int[] inorder = {4, 2, 5, 8, 1, 6, 3, 7};
TreeNode root = buildTree(preorder, inorder);
//调用遍历方法
}
}
内容总结
以上是互联网集市为您收集整理的数据结构树及相关算法题全部内容，希望文章能够帮你解决数据结构树及相关算法题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】