非递归遍历二叉树Java
2022/6/28 14:20:26
本文主要是介绍非递归遍历二叉树Java,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
import java.util.*; public class Test { static class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } } public static void main(String[] args) { TreeNode treeNode1 = new TreeNode(1); TreeNode treeNode2 = new TreeNode(2); TreeNode treeNode3 = new TreeNode(3); TreeNode treeNode4 = new TreeNode(4); TreeNode treeNode5 = new TreeNode(5); TreeNode treeNode6 = new TreeNode(6); TreeNode treeNode7 = new TreeNode(7); treeNode1.left = treeNode2; treeNode1.right = treeNode3; treeNode2.left = treeNode4; treeNode2.right = treeNode5; treeNode3.left = treeNode6; treeNode3.right = treeNode7; List<Integer> f = in(treeNode1); System.out.println(f); System.out.println(pre(treeNode1)); System.out.println(post(treeNode1)); } /** * 中序遍历 非递归 */ public static List<Integer> in(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stk = new Stack<TreeNode>(); TreeNode p = root; while (p != null || !stk.isEmpty()) { while (p != null) { stk.push(p); p = p.left; } p = stk.pop(); res.add(p.val); p = p.right; } return res; } /** * 非递归先序 */ public static List<Integer> pre(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stk = new Stack<TreeNode>(); stk.push(root); TreeNode p = root; while (!stk.isEmpty()) { p = stk.pop(); res.add(p.val); if (p.right != null) { stk.push(p.right); } if (p.left != null) { stk.push(p.left); } } return res; } /** * 非递归后续遍历 */ public static List<Integer> post(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stk = new Stack<TreeNode>(); TreeNode p = root; TreeNode prev = null; while (p != null || !stk.isEmpty()) { while (p != null) { stk.push(p); p = p.left; } p = stk.pop(); if (p.right == null || p.right == prev) { res.add(p.val); prev = p; p = null; } else { stk.push(p); p = p.right; } } return res; } }
这篇关于非递归遍历二叉树Java的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?