二叉树的inorder实现：递归、栈、Morris遍历

不包含null值检查等robust代码。

递归：

inorderTreeWalk(TreeNode root) { if(root != null) { inorderTreeWalk(root.left); System.out.println(root.val); inorderTreeWalk(root.right); } }

栈：

inorderTreeWalk(TreeNode root) { Stack<TreeNode> stack = new Stack<TreeNode>(); while(root!=null || !stack.isEmpty()) { while(root != null) { stack.push(root); root = root.left; } System.out.println(stack.pop().val); root = root.right; } }

Morris遍历：

TreeNode pre = null; while(root != null) { //如果root的左子树为空，直接访问该节点，然后访问右子树 if(root.left == null) { System.out.println(root.val); root = root.right; continue; } //寻找root的前驱节点 for(pre=root.left; pre.right != null && pre.right!=root; pre=pre.right); //如果是第一次访问pre，则建立thread（线索）：将pre.right指向root if(pre.right == null) { pre.right = root; root = root.left; } else { //第二次访问，说明左子树已经访问过了 pre.right = null; System.out.println(root.val); root = root.right; } }