首页 > 代码库 > Leetcode: Binary Tree Inorder Transversal
Leetcode: Binary Tree Inorder Transversal
Given a binary tree, return the inorder traversal of its nodes‘ values.For example:Given binary tree {1,#,2,3}, 1 2 / 3return [1,3,2].Note: Recursive solution is trivial, could you do it iteratively?
难度：50
recursive 方法：
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public List<Integer> inorderTraversal(TreeNode root) {12 ArrayList<Integer> res = new ArrayList<Integer>();13 if (root == null) return res;14 helper(root, res);15 return res;16 }17 18 public void helper(TreeNode root, ArrayList<Integer> res) {19 if (root == null) {20 return;21 }22 if (root.left != null) {23 helper(root.left, res);24 }25 res.add(root.val);26 if (root.right != null) {27 helper(root.right, res);28 }29 }30 }
Iterative method: 参考了一下网上的思路，其实就是用一个栈来模拟递归的过程。所以算法时间复杂度也是O(n)，空间复杂度是栈的大小O(logn)。
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public List<Integer> inorderTraversal(TreeNode root) {12 ArrayList<Integer> result = new ArrayList<Integer>();13 if (root == null) return result;14 LinkedList<TreeNode> stack = new LinkedList<TreeNode>();15 while (root != null || !stack.isEmpty()) {16 if (root != null) {17 stack.push(root);18 root = root.left;19 }20 else {21 root = stack.pop();22 result.add(root.val);23 root = root.right;24 }25 }26 return result;27 }28 }
Leetcode: Binary Tree Inorder Transversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。