04月 01 数据结构 二叉树中序遍历 发表于 2018-04-01 • 字数统计: 二叉树中序遍历二叉树中序遍历:先遍历左子树,然后访问根节点,最后遍历右子树 递归实现中序遍历(Java)12345678910111213141516171819202122232425/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); pre(root,result); return result; } public void pre(TreeNode root, List<Integer> result){ if(root == null){ return; } pre(root.left,result); result.add(root.val); pre(root.right,result); }} 堆栈迭代实现中序遍历(Java)1234567891011121314151617181920212223242526/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode curr = root; while(curr != null || !stack.isEmpty()){ while(curr != null){ stack.push(curr); curr = curr.left; } curr = stack.pop(); result.add(curr.val); curr = curr.right; } return result; }} 分享到: 赞赏 微信扫一扫,向我赞赏 支付宝扫一扫,向我赞赏