【Leetcode】94. Binary Tree Inorder Traversal

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:



最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容