JAVA实现树的遍历

各位大佬们最近有在找工作的吗？行情咋样啊，想先了解一下情况。

2022年CSP-J1 CSP-S1 第1轮初赛 报名指南​​​​​​2022年CSP-J1 CSP-S1 第1轮初赛 报名指南_dllglvzhenfeng的博客-CSDN博客【教程】图文详解 CSP-J/S 第一轮报名流程（附备考建议）【教程】图文详解 CSP-J/S 第一轮报名流程（附备考建议）CSP J/S你真的报名成功了吗？报名步骤详解速看！CSP J/S你真的报名成功了吗？报名步骤详解速看！ - 知乎0.CSP-J初赛集训第0课——进制转换0.CSP-J初赛集训第0课——进制转换_哔哩哔哩_bilibili1.CSP-J初赛集训第1课——计算机中的数据大小1.CSP-J初赛集训第1课——计算机中的数据大小_哔哩哔哩_bilibili2.CSP-J初赛集训第2课 原码反码与补码2.CSP-J初赛集训第2课 原码反码与补码_哔哩哔哩_bilibili3.CSP-J初赛集训第3课 进制转换 原码反码补码 近十年真题汇总3.CSP-J初赛集训第3课 进制转换 原码反码补码 近十年真题汇总_哔哩哔哩_bilibili4.CSP-J初赛集训第4课——栈和队列初识4.CSP-J初赛集训第4课——栈和队列初识_哔哩哔哩_bilibili5.CSP-J初赛集训—栈的近20年真题讲解5.CSP-J初赛集训—栈的近20年真题讲解_哔哩哔哩_bilibili6.CSP-J初赛集训——循环队列 真题讲解6.CSP-J初赛集训——循环队列 真题讲解_哔哩哔哩_bilibili7.CSP-J初赛集训第5课 数据结构 树的基本概念介绍 树和二叉树 小白一听就会7.CSP-J初赛集训第5课 数据结构 树的基本概念介绍 树和二叉树 小白一听就会_哔哩哔哩_bilibili8.CSP-J初赛集训 关于树的计算真题 二叉树的计算 CSP noip8.CSP-J初赛集训 关于树的计算真题 二叉树的计算 CSP noip_哔哩哔哩_bilibili9.CSP-J初赛集训第6课 二叉树的遍历 小白入门必好学9.CSP-J初赛集训第6课 二叉树的遍历 小白入门必好学_哔哩哔哩_bilibili10.CSP-J初赛集训 二叉树的遍历 历年真题讲解10.CSP-J初赛集训 二叉树的遍历 历年真题讲解_哔哩哔哩_bilibili11.CSP-J初赛集训第6课 图的基本概念介绍11.CSP-J初赛集训第6课 图的基本概念介绍_哔哩哔哩_bilibili12.CSP-J初赛集训 关于图的历年真题讲解12.CSP-J初赛集训 关于图的历年真题讲解_哔哩哔哩_bilibili13.CSP-J初赛集训第7课_排列和组合13.CSP-J初赛集训第7课_排列和组合_哔哩哔哩_bilibili14.CSP-J初赛排列和组合历年真题114.CSP-J初赛排列和组合历年真题1_哔哩哔哩_bilibili15.CSP-J初赛排列和组合历年真题215.CSP-J初赛排列和组合历年真题2_哔哩哔哩_bilibili16.CSP-J初赛排列和组合历年真题3​​​​​​16.CSP-J初赛排列和组合历年真题3_哔哩哔哩_bilibili17.CSP-J初赛数学问题历年真题17.CSP-J初赛数学问题历年真题_哔哩哔哩_bilibili信奥学习规划 信息学竞赛之路(2022.07.31)信奥学习规划 信息学竞赛之路(2022.07.31)_dllglvzhenfeng的博客-CSDN博客Scratch -＞ C++画图-＞信奥（C++）学习导航Scratch -＞ C++画图-＞信奥（C++）学习导航_dllglvzhenfeng的博客-CSDN博客【NOI2022】PV「什么是信息学精神？」【NOI2022】PV「什么是信息学精神？」_dllglvzhenfeng的博客-CSDN博客高含金量国际计算机编程竞赛高含金量国际计算机编程竞赛_dllglvzhenfeng的博客-CSDN博客_计算机编程大赛【国际竞赛-计算机篇】2022年高含金量的计算机竞赛有哪些【国际竞赛-计算机篇】2022年高含金量的计算机竞赛有哪些_dllglvzhenfeng的博客-CSDN博客Kaggle学习Kaggle学习_dllglvzhenfeng的博客-CSDN博客Scratch -＞ C++画图-＞信奥（C++）学习导航Scratch -＞ C++画图-＞信奥（C++）学习导航_dllglvzhenfeng的博客-CSDN博客USACO资料集（2022.07.22）USACO资料集（2022.07.22）_dllglvzhenfeng的博客-CSDN博客【信息学奥赛】2021 CSP-J 初赛真题解析【信息学奥赛】2021 CSP-J 初赛真题解析_哔哩哔哩_bilibili【合集】信息学奥赛 2020 CSP-J 初赛真题解析【合集】信息学奥赛 2020 CSP-J 初赛真题解析_哔哩哔哩_bilibili【合集】信息学奥赛 2019 CSP-J 初赛真题解析【合集】信息学奥赛 2019 CSP-J 初赛真题解析_哔哩哔哩_bilibiliCSP-J初赛集训（因特网概述）CSP-J初赛集训（因特网概述）_哔哩哔哩_bilibili信奥（CSP-J/S初赛）公益讲座精选系列之考点和重点信奥（CSP-J/S初赛）公益讲座精选系列之考点和重点_哔哩哔哩_bilibili信奥集训营【CSP-J专题集训、案例全、历年真题讲解、值得收藏】信奥集训营【CSP-J专题集训、案例全、历年真题讲解、值得收藏】_哔哩哔哩_bilibili初赛大题选讲——信奥（CSP-J/S初赛）公益讲座精选系列初赛大题选讲——信奥（CSP-J/S初赛）公益讲座精选系列_哔哩哔哩_bilibili2022csp-j初赛模拟day082022csp-j初赛模拟day08_哔哩哔哩_bilibili2022csp-j初赛模拟day092022csp-j初赛模拟day09_哔哩哔哩_bilibili2021CSP-J第一轮认证分析与吐槽2021CSP-J第一轮认证分析与吐槽_哔哩哔哩_bilibili名师教你学 - NOIP 信息学奥赛 CSP-J 刷题班名师教你学 - NOIP 信息学奥赛 CSP-J 刷题班_哔哩哔哩_bilibili聊聊2021年csp-j初赛的事儿聊聊2021年csp-j初赛的事儿_哔哩哔哩_bilibiliCSP-J初赛知识点：其它进制CSP-J初赛知识点：其它进制_哔哩哔哩_bilibili信息学奥赛CSP-J：链表专题信息学奥赛CSP-J：链表专题_哔哩哔哩_bilibili2023计算机考研专业课参考书目（408）2023计算机考研专业课参考书目（408）_dllglvzhenfeng的博客-CSDN博客_计算机408参考教材计算机考研 机试书籍及相关的资料计算机考研 机试书籍及相关的资料_dllglvzhenfeng的博客-CSDN博客2023年 计算机考研 资料集（2022.02.03）2023年 计算机考研 资料集（2022.02.03）_dllglvzhenfeng的博客-CSDN博客动画学信奥 漫画学算法 CSP-J入门级 （一）、计算机基础与编程环境（依据「NOI大纲」）动画学信奥 漫画学算法 CSP-J入门级 （一）、计算机基础与编程环境（依据「NOI大纲」）_dllglvzhenfeng的博客-CSDN博客_cspj考试大纲动画学信奥 漫画学算法 CSP-J入门级 （二）、C++程序设计 数据结构（依据「NOI大纲」）动画学信奥 漫画学算法 CSP-J入门级 （二）、C++程序设计 数据结构（依据「NOI大纲」）_dllglvzhenfeng的博客-CSDN博客_csp-j 数据结构动画学信奥 漫画学算法 CSP-J入门级 （三）、算法（依据「NOI大纲」）动画学信奥 漫画学算法 CSP-J入门级 （三）、算法（依据「NOI大纲」）_dllglvzhenfeng的博客-CSDN博客————————————————版权声明：本文为CSDN博主「dllglvzhenfeng」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/dllglvzhenfeng/article/details/126253377

class TreeNode {    int data;    TreeNode left;    TreeNode right;    public TreeNode() {}    public TreeNode(int data) {        this.data = data;    }}

//中左右public static void preOrder(TreeNode root) {    if (root == null) return;    System.out.print(root.data + " ");    preOrder(root.left);    preOrder(root.right);}//左中右public static void midOrder(TreeNode root) {    if (root == null) return;    midOrder(root.left);    System.out.print(root.data + " ");    midOrder(root.right);}//左右中public static void postOrder(TreeNode root) {    if (root == null) return;    postOrder(root.left);    postOrder(root.right);    System.out.print(root.data + " ");}

//中左右public static void preOrder(TreeNode root) {    if (root == null) return;    System.out.print(root.data + " ");    preOrder(root.left);    preOrder(root.right);}//左中右public static void midOrder(TreeNode root) {    if (root == null) return;    midOrder(root.left);    System.out.print(root.data + " ");    midOrder(root.right);}//左右中public static void postOrder(TreeNode root) {    if (root == null) return;    postOrder(root.left);    postOrder(root.right);    System.out.print(root.data + " ");}

//中左右 => 右左(中空)public static void preOrder(TreeNode root) {    if (root == null) return;    Stack stack = new Stack<>();    stack.push(root);    while (!stack.isEmpty()) {        TreeNode node = stack.pop();        if (node != null) {            if (node.right != null) stack.push(node.right);            if (node.left != null) stack.push(node.left);            stack.push(node);            stack.push(null);        } else {            node = stack.pop();            System.out.print(node.data + " ");        }    }}//左中右 => 右(中空)左public static void midOrder(TreeNode root) {    if (root == null) return;    Stack stack = new Stack<>();    stack.push(root);    while (!stack.isEmpty()) {        TreeNode node = stack.pop();        if (node != null) {            if (node.right != null) stack.push(node.right);            stack.push(node);            stack.push(null);            if (node.left != null) stack.push(node.left);        } else {            node = stack.pop();            System.out.print(node.data + " ");        }    }}//左右中 => (中空)右左public static void postOrder(TreeNode root) {    if (root == null) return;    Stack stack = new Stack<>();    stack.push(root);    while (!stack.isEmpty()) {        TreeNode node = stack.pop();        if (node != null) {            stack.push(node);            stack.push(null);            if (node.right != null) stack.push(node.right);            if (node.left != null) stack.push(node.left);        } else {            node = stack.pop();            System.out.print(node.data + " ");        }    }}

Morris的整体思路就是将 以某个根结点开始，找到它左子树的最右侧节点之后与这个根结点进行连接我们可以从 图2 看到，如果这么连接之后，cur 这个指针是可以完整的从一个节点顺着下一个节点遍历，将整棵树遍历完毕，直到 7 这个节点右侧没有指向。

2021-04-14：判断二叉树是否是满二叉树？

2021-04-13：判断二叉树是否是平衡二叉树？

2021-04-12：判断二叉树是否是搜索二叉树？

2021-04-11：判断二叉树是否是完全二叉树？

华为云博客地址：https://bbs.huaweicloud.com/blogs/254847 二叉树的递归思想很重要，还有递归的复杂度分析 - [1.1 二叉树的初始化](#11-二叉树的初始化) - [1.2 创建一个二叉树](#12-创建一个二叉树) - [1.3 前序遍历](#13-前序遍历) - [1.4 中序遍历](#14-中序遍历) - [1.5 后序遍历](#15-后序遍历) - [1.6 层序遍历](#16-层序遍历) - [1.7 计算节点数](#17-计算节点数) - [1.8 计算树的深度](#18-计算树的深度) - [1.9 计算树的叶子树](#19-计算树的叶子树) - [1.10 获取第K层节点数](#110-获取第k层节点数) - [1.11 判断两颗二叉树是否相同](#111-判断两颗二叉树是否相同) - [1.12 二叉树的镜像](#112-二叉树的镜像) - [1.13 找最低公共祖先节点](#113-找最低公共祖先节点) - [1.14 获取两个节点的距离](#114-获取两个节点的距离) - [1.15 找一个节点的所有祖宗节点](#115-找一个节点的所有祖宗节点) # 1.1 二叉树的初始化 ``` #initial of BinaryTree class BinaryTree: def __init__(self,rootObj): self.val = rootObj self.left = None self.right = None def insertLeft(self,newNode): if self.left == None: self.left = BinaryTree(newNode) else: t = BinaryTree(newNode) t.left = self.left self.left = t def insertRight(self,newNode): if self.right == None: self.right = BinaryTree(newNode) else: t = BinaryTree(newNode) t.right = self.right self.right = t ``` # 1.2 创建一个二叉树 ``` #create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4] # 18 # 7 11 #3 4 5 6 # 1 3 2 4 root = BinaryTree(18) root.left = BinaryTree(7) root.right = BinaryTree(11) root.left.left = BinaryTree(3) root.left.right = BinaryTree(4) root.right.left = BinaryTree(5) root.right.right = BinaryTree(6) root.right.left.left = BinaryTree(1) root.right.left.right = BinaryTree(3) root.right.right.left = BinaryTree(2) root.right.right.right = BinaryTree(4) ``` # 1.3 前序遍历 ``` #递归版本 def PreOrder(self, node): if node: print(node.val) self.PreOrder(node.left) self.PreOrder(node.right) #循环版本 def PreOrderLoop(self, node): if node == None: return stack =[] print(node.val) stack.append(node) node = node.left while stack!=[] or node: while node: print(node.val) stack.append(node) node = node.left node = stack[-1].right stack.pop() #ouput: 18 7 3 4 11 5 1 3 6 2 4 ``` # 1.4 中序遍历 ``` #递归版本 def InOrder(self, node): if node: self.InOrder(node.left) print(node.val) self.InOrder(node.right) #循环版本 def InOrderLoop(self, node): if node == None: return None stack = [] stack.append(node) node = node.left while stack!=[] or node: while node: stack.append(node) node = node.left print(stack[-1].val) node = stack[-1].right stack.pop() #output：3 7 4 18 1 5 3 11 2 6 4 ``` # 1.5 后序遍历 ``` #递归 def PostOrder(self, node): if node: self.PostOrder(node.left) self.PostOrder(node.right) print(node.val) #非递归 def PostOrderLoop(self, node): if node == None: return stack =[] stack.append(node) pre = None while stack!=[]: node = stack[-1] if ((node.left==None and node.right==None) or (pre and (pre == node.left or pre ==node.right))): print(node.val) pre = node stack.pop() else: if node.right: stack.append(node.right) if node.left: stack.append(node.left) #output:3 4 7 1 3 5 2 4 6 11 18 ``` # 1.6 层序遍历 ``` def LevelOrder(self, node): if node == None: return stack = [] stack.append(node) while stack!=[]: node = stack[0] if node.left: stack.append(node.left) if node.right: stack.append(node.right) print(node.val) stack.pop(0) output: 18 7 11 3 4 5 6 1 3 2 4 ``` # 1.7 计算节点数 ``` #递归版本 def CountNode(self, root): if root == None: return 0 return self.CountNode(root.left) + self.CountNode(root.right) + 1 #非递归版本 def CountNodeNotRev(self, root): if root == None: return 0 stack = [] stack.append(root) index = 0 while index print(len(stack)) output: 11 ``` # 1.8 计算树的深度 ``` def getTreeDepth(self, root): if root == None: return 0 left = self.getTreeDepth(root.left) + 1 right = self.getTreeDepth(root.right) + 1 return left if left>right else right ``` # 1.9 计算树的叶子树 ``` def countLeaves(self, root): if root == None: return 0 if root.left==None and root.right==None: return 1 return self.countLeaves(root.left)+self.countLeaves(root.right) ``` # 1.10 获取第K层节点数 ``` def getKLevel(self, root, K): if root == None: return 0 if K == 1: return 1 return self.getKLevel(root.left, K-1)+self.getKLevel(root.right, K-1) ``` # 1.11 判断两颗二叉树是否相同 ``` def StrucCmp(self, root1, root2): if root1 == None and root2 == None: return True elif root1 ==None or root2 == None: return False return self.StrucCmp(root1.left, root2.left) and self.StrucCmp(root1.right, root2.right) ``` # 1.12 二叉树的镜像 ``` def Mirror(self, root): if root == None: return tmp = root.left root.left = root.right root.right = tmp self.Mirror(root.left) self.Mirror(root.right) ``` # 1.13 找最低公共祖先节点 ``` def findLCA(self, root, node1, node2): if root == None: return if root == node1 or root == node2: return root left = self.findLCA(root.left, node1, node2) right = self.findLCA(root.right, node1, node2) if left and right: return root return left if left else right ``` # 1.14 获取两个节点的距离 ``` def getDist(self, root, node1, node2): lca = self.findLCA(root, node1, node2) #找最低公共祖宗节点 level1 = self.FindLevel(lca, node1) #祖节点到两个节点的距离 level2 = self.FindLevel(lca, node2) return level1+level2 def FindLevel(self, node, target): if node == None: return -1 if node == target: return 0 level = self.FindLevel(node.left, target) if level == -1: level = self.FindLevel(node.right, target) if level != -1: return level + 1 return -1 ``` # 1.15 找一个节点的所有祖宗节点 ``` def findAllAncestor(self, root, target): if root == None: return False if root == target: return True if self.findAllAncestor(root.left, target) or self.findAllAncestor(root.right, target): print(root.val) return True return False ```

恭喜你顺利进入第三间，线索如下： 如下列二叉树所示，使用前序遍历补齐下列url字符串，以获取第四间的url地址 待补齐的url：   https://bbs.huaweicloud.com/ 二叉树：此帖不用回复！

2021-03-21：给定一棵二叉树的头节点head，求以head为头的树中，最小深度是多少？