算法题-二叉树的中序遍历

题目链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/ 题目描述： 给定一个二叉树，返回它的中序 遍历。

示例:

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

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解法一

通过递归实现。时间复杂度：O(N)，空间复杂度：平均是O(logn)（树的高度）。最坏是O(n)（当树退化成链表时）。

/** * 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> ans = new ArrayList<>(); //调用中序遍历方法 inorder(root,ans); return ans; } private void inorder(TreeNode root,List<Integer> ans) { if(root != null) { //左结点不为空，遍历左子树 if(root.left != null) { inorder(root.left , ans); } //访问根结点 ans.add(root.val); //右节点不为空，访问右子树 if(root.right != null) { inorder(root.right , ans); } } } }

解法二

利用栈，使用迭代。时间复杂度：O(N)。空间复杂度：O(n)。

/** * 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> ans = new ArrayList<>(); Deque<TreeNode> stack = new LinkedList<>(); TreeNode current = root; while(current != null || !stack.isEmpty()) { //将当前节点的左孩子入栈，直到没有左孩子 while(current != null) { stack.offerFirst(current); current = current.left; } //当左孩子都入栈之后，将之出栈，并将其值加入ans，将其右孩子入栈 current = stack.pollFirst(); ans.add(current.val); //如果当前节点没有右孩子，则进入下一次循环，将其父节点出栈返回。 current = current.right; } return ans; } }

解法三

使用栈、迭代。但是将先序、中序和后序遍历的迭代式代码统一了。 只需更改右孩子、当前节点、左孩子的入栈顺序，就可以实现三种遍历方式。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ //定义一个类，表示结点与其对应颜色 public class ColorNode { TreeNode node; String color; public ColorNode(TreeNode node,String color) { this.node = node; this.color = color; } } //第一次遍历到的结点都设置为白色“white” //第二次遍历到的结点设置为灰色“gray” //如果遇到白色的结点，更改其颜色为灰色，并将其右孩子、自身、左孩子分别入栈 //如果遇到灰色结点，将其值加入ans中 class Solution { public List<Integer> inorderTraversal(TreeNode root) { if(root == null){ return new ArrayList<Integer>(0); } List<Integer> ans = new ArrayList<>(); Deque<ColorNode> stack = new LinkedList<>(); //把根结点设置为白色，放入栈中 stack.offerFirst(new ColorNode(root,"white")); while(!stack.isEmpty()) { //将栈顶元素出栈 ColorNode cn = stack.pollFirst(); //遇到白色结点 if(cn.color.equals("white")) { //当前节点有右孩子，将右孩子设置为白色，入栈 if(cn.node.right != null) { stack.offerFirst(new ColorNode(cn.node.right,"white")); } //将当前结点更改为灰色，入栈 stack.offerFirst(new ColorNode(cn.node,"gray")); //如果当前结点有左孩子，将左孩子设置为白色，入栈 if(cn.node.left != null) { stack.offerFirst(new ColorNode(cn.node.left,"white")); } } //遇到灰色结点，将其值加入ans中 else { ans.add(cn.node.val); } } return ans; } }