写算法的前提是的搞清楚这个算法的思路到底是啥，比如这个，这个二叉树的中序遍历，自己都没搞清楚到底是怎么遍历的，就开始写代码，这样是徒劳的，搞清楚该题的问题，需求，然后想出思路，再开始写题
还有递归，虽然说一步步来不可取，但是，可以把数据尽量减少，然后一步步来看是否合适，或者调试。
import java.util.ArrayList; import java.util.List; /** * @Author: llb * @Date: 2020/10/19 10:42 */ public class InorderTraversal { int val; InorderTraversal left; InorderTraversal right; InorderTraversal() {} InorderTraversal(int val) { this.val = val; } InorderTraversal(int val, InorderTraversal left, InorderTraversal right) { this.val = val; this.left = left; this.right = right; } public static void main(String[] args) { InorderTraversal root = new InorderTraversal(1); InorderTraversal root2 = new InorderTraversal(2); InorderTraversal root3 = new InorderTraversal(3); root.right = root2; root2.left = root3; List<Integer> list = inOrderTraversal(root); System.out.println(list); } public static List<Integer> inOrderTraversal (InorderTraversal root) { List<Integer> res = new ArrayList<>(); inorder(root, res); return res; } public static void inorder (InorderTraversal node, List<Integer> res) { if (null == node) { return ; } // 这里是相当于将该节点的子树全部，按照中序遍历之后，再将该节点的id放入集合，做到了，先左子树再根节点，然后再又子树 // 如果左子树为空，那么就是将根节点添加结果集，然后再遍历该节点的右子树 // 中序遍历：整体的思路就是，先左，再根，再右 inorder(node.left, res); res.add(node.val); inorder(node.right, res); } }时间复杂度：O(N),N为二叉树的节点数，在遍历中，每个节点都被使用且只使用了一次。 空间复杂度：O(n)O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n)O(n) 的级别。
