极客时间-算法训练营 学习笔记 2.2 实战题目解析：二叉树的中序遍历

一 序

  本文属于极客时间-算法训练营 学习笔记。

上节课学习了树、二叉树、二叉搜索树的实现

本节课学习做题

二 二叉树的中序遍历

一 题目：

94. Binary Tree Inorder Traversal

Medium

3067130Add to ListShare

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

中序遍历。好了思考1分钟：

回顾下模板：

开搞

不习惯LeetCode，可以先在ide上写一遍。

public class Code94 { public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); DSF(list,root); return list; } public void DSF( List<Integer> list,TreeNode node ){ if(node == null){ return; } DSF(list,node.left); list.add(node.val); DSF(list,node.right); } }

覃超老师纠正自己的一个观点。就是摘掉对于递归的有色眼镜。

再尾递归的优化下，递归本身效率跟for循环没有太多区别。

举个费锲那波数列的问题，锅不应该有递归来背，而是自己把程序写残了。

把一个线性的复杂度给写成指数的。

你看，学到一个点，就值回9.9了。

关于另外一种方式：除了官方的Morris 遍历外（这个不作要求）。

就是栈了。这里要理解，递归是系统替我们维护了一个栈，把数据传进入。

改用栈的方式。这里我翻车了，没做出来，记了官方的solution。

但是我个人觉得不容易理解。