发布于2021-03-07 20:41 阅读(847) 评论(0) 点赞(13) 收藏(3)
判断树中结点个数 public static <T> int getTreeNum(TreeNode<T> root)
判断树中结点个数 public static int getTreeNum(TreeNode root)
return getTreeNum(root.leftChild) + getTreeNum(root.rightChild) + 1;
判断树的深度 public static int getTreeDepth(TreeNode root)
int leftDepth = getTreeDepth(root.leftChild) + 1;
int rightDepth = getTreeDepth(root.rightChild) + 1;
return Math.max(leftDepth, rightDepth);
前序遍历 public static void preOrderTravel(TreeNode root)
if (root == null) {
return;
}
visitNode(root);
preOrderTravel(root.leftChild);
preOrderTravel(root.rightChild);
中序遍历 public static void midOrderTravel(TreeNode root)
if (root == null) {
return;
}
midOrderTravel(root.leftChild);
visitNode(root);
midOrderTravel(root.rightChild);
后序遍历 public static void backOrderTravel(TreeNode root)
if (root == null) {
return;
}
midOrderTravel(root.leftChild);
midOrderTravel(root.rightChild);
visitNode(root);
层次遍历 public static void levelTravel(TreeNode root)
Queue<TreeNode<T>> q = new LinkedList();
q.offer(root); //入队列
while (!q.isEmpty()) {
TreeNode<T> temp = q.poll(); //出队列
visitNode(temp);
if (temp.leftChild != null) {
q.offer(temp.leftChild);
}
if (temp.rightChild != null) {
q.offer(temp.rightChild);
}
}
访问node结点 private static void visitNode
System.out.print(node.value + "\t");
求第K层结点个数 public static int getNumForKlevel(TreeNode root, int k)
int leftNum = getNumForKlevel(root.leftChild, k - 1);
int rightNum = getNumForKlevel(root.rightChild, k - 1);
return leftNum + rightNum;
根据前序和中序构建二叉树(有点难度哦!)
//TreeNode<Integer> root = TreeTools.getTreeFromPreAndMid(pre, mid);
//pre = [1, 2, 4, 5, 3] mid = [4, 2, 5, 1, 3]
public static <T> TreeNode<T> getTreeFromPreAndMid(List<T> pre, List<T> mid) {
if (pre == null || mid == null || pre.size() == 0 || mid.size() == 0) {
return null;
}
if (pre.size() == 1) {
return new TreeNode<T>(pre.get(0));
}
TreeNode<T> root = new TreeNode<T>(pre.get(0));
// 找出根节点在中序中的位置
int index = 0;
while (!mid.get(index++).equals(pre.get(0))) {
}
// 构建左子树的前序
List<T> preLeft = new ArrayList<T>(index); //index = 3
// 左子树的中序
List<T> midLeft = new ArrayList<T>(index);
for (int i = 1; i < index; i++) {
preLeft.add(pre.get(i));
}
for (int i = 0; i < index - 1; i++) {
midLeft.add(mid.get(i));
}
// 重建左子树
root.leftChild = getTreeFromPreAndMid(preLeft, midLeft);
// 右子树的前序
List<T> preRight = new ArrayList<T>(pre.size() - index - 1);
// 右子树的中序
List<T> midRight = new ArrayList<T>(pre.size() - index - 1);
for (int i = 0; i <= pre.size() - index - 1; i++) {
preRight.add(pre.get(index + i));
}
for (int i = 0; i <= pre.size() - index - 1; i++) {
midRight.add(mid.get(index + i));
}
// 重建→子树
root.rightChild = getTreeFromPreAndMid(preRight, midRight);
return root;
}
原文链接:https://blog.csdn.net/AC_872767407/article/details/114415353
作者:javabb
链接:http://www.javaheidong.com/blog/article/110649/5fb320e940624e545fa9/
来源:java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 java黑洞网 All Rights Reserved 版权所有,并保留所有权利。京ICP备18063182号-2
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!