binary-tree-inorder-traversal ゞ 浴缸里的玫瑰 2021-11-09 08:36 149阅读 0赞 /\*\* \* \* @author gentleKay \* Given a binary tree, return the inorder traversal of its nodes' values. \* For example: \* Given binary tree\{1,\#,2,3\}, 1 \\ 2 / 3 \* return\[1,3,2\]. \* Note: Recursive solution is trivial, could you do it iteratively? \* confused what"\{1,\#,2,3\}"means? > read more on how binary tree is serialized on OJ. \* 给定二叉树,返回其节点值的中序遍历。 \* 例如: \* 给定二叉树1,,2,3, \* 返回\[1,3,2\]。 \* 注意:递归解决方案很简单,可以迭代吗? \*/ ### 推荐一个博客(关于递归和非递归二叉树的遍历) ### ### [https://blog.csdn.net/wang454592297/article/details/79472938][https_blog.csdn.net_wang454592297_article_details_79472938] ### #### 方法一:(非递归进行中序遍历) #### import java.util.ArrayList; import java.util.Stack; /** * * @author gentleKay * Given a binary tree, return the inorder traversal of its nodes' values. * For example: * Given binary tree{1,#,2,3}, 1 \ 2 / 3 * return[1,3,2]. * Note: Recursive solution is trivial, could you do it iteratively? * confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ. * 给定二叉树,返回其节点值的中序遍历。 * 例如: * 给定二叉树1,,2,3, * 返回[1,3,2]。 * 注意:递归解决方案很简单,可以迭代吗? */ public class Main21 { public static void main(String[] args) { // TODO Auto-generated method stub // TreeNode root = null; TreeNode root = new TreeNode(4); root.left = new TreeNode(2); root.left.left = new TreeNode(1); root.left.right = new TreeNode(3); root.right = new TreeNode(6); root.right.left = new TreeNode(5); root.right.right = new TreeNode(7); root.right.right.right = new TreeNode(8); System.out.println(Main21.inorderTraversal(root)); } public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public static ArrayList<Integer> inorderTraversal(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); ArrayList<Integer> array = new ArrayList<>(); while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } if (!stack.isEmpty()) { root = stack.pop(); array.add(root.val); root = root.right; } } return array; } } #### 方法二:(递归进行中序遍历) #### import java.util.ArrayList; import java.util.Stack; /** * * @author gentleKay * Given a binary tree, return the inorder traversal of its nodes' values. * For example: * Given binary tree{1,#,2,3}, 1 \ 2 / 3 * return[1,3,2]. * Note: Recursive solution is trivial, could you do it iteratively? * confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ. * 给定二叉树,返回其节点值的中序遍历。 * 例如: * 给定二叉树1,,2,3, * 返回[1,3,2]。 * 注意:递归解决方案很简单,可以迭代吗? */ public class Main21 { public static void main(String[] args) { // TODO Auto-generated method stub // TreeNode root = null; TreeNode root = new TreeNode(4); root.left = new TreeNode(2); root.left.left = new TreeNode(1); root.left.right = new TreeNode(3); root.right = new TreeNode(6); root.right.left = new TreeNode(5); root.right.right = new TreeNode(7); root.right.right.right = new TreeNode(8); System.out.println(Main21.inorderTraversal(root)); } public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } static ArrayList<Integer> array = new ArrayList<>(); public static ArrayList<Integer> inorderTraversal(TreeNode root) { if (root == null) { return array; } ergodic(root); return array; } public static void ergodic(TreeNode root) { if (root.left != null) { ergodic(root.left); } array.add(root.val); if (root.right != null) { ergodic(root.right); } } } 转载于:https://www.cnblogs.com/strive-19970713/p/11271596.html [https_blog.csdn.net_wang454592297_article_details_79472938]: https://blog.csdn.net/wang454592297/article/details/79472938
还没有评论,来说两句吧...