【LeetCode】94. 二叉树的中序遍历

此题连接

题目描述 给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3] 输出: [1,3,2]

题解 直接递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { List<Integer> list = new ArrayList<Integer>(); public List<Integer> inorderTraversal(TreeNode root) { if(root!=null){ inorderTraversal(root.left); list.add(root.val); inorderTraversal(root.right); } return list; } }

非递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { List<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); public List<Integer> inorderTraversal(TreeNode root) { while(root!=null || !stack.isEmpty()){ if(root!=null){ stack.push(root); root=root.left; }else{ root=stack.pop(); list.add(root.val); root=root.right; } } return list; } }

不递归，不用栈，耗时和递归一样

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { List<Integer> list = new ArrayList<Integer>(); public List<Integer> inorderTraversal(TreeNode root) { while(root!=null){ if(root.left == null){ list.add(root.val); root = root.right; } else{ TreeNode prev = root.left; while(prev.right != null && prev.right != root) prev = prev.right; if(prev.right == null){ prev.right = root; root = root.left; } else{ prev.right = null; list.add(root.val); root = root.right; } } } return list; } }