Given a binary tree, return the inorder traversal of its nodes' values.
1 使用recursive方法:依次从root递归下去,定义一个函数,输入二叉树,返回得到的node value,因为是inorder traversal, 所以先返回左子树,再返回root.val,再返回右子树,对于左子树和右子树,再调用这个递归函数
2 为什么要单独写一个函数?单独写的这个函数有返回值
3 iterative的方法:先将根节点和所有左子树的根节点压到栈中, 首先pop最左端的左子节点,然后pop这个子节点的根节点,继续将这个根节点的右节点压到栈中,压栈的方法和之前的一样,压左节点,然后再pop,依次循环这个过程,当栈里面的元素都pop完以后,就返回res
4 iterative的方法,因为对每一个节点都进行了压栈和pop的过程,所以时间复杂度是O(n)
5 recursive的方法就是要注意上述红框,因为是list的concatenate,所以要用[]括起来
6 iterative: