专栏首页木又AI帮打卡群2刷题总结1009——二叉树的中序遍历

打卡群2刷题总结1009——二叉树的中序遍历

leetcode第94题:二叉树的中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

【题目】

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

【思路】

前序遍历、中序遍历、后序遍历,这三种遍历方式中,前中后指的都是根节点的顺序,并且都是先遍历左子树、再遍历右子树。

中序遍历递归解法:先递归遍历左子树,再访问当前节点的值,最后递归遍历右子树。

中序遍历非递归解法:使用两个栈,一个栈(栈1)存储节点,另一个栈(栈2)存储访问标签。要想实现左根右的顺序,则需要先插入右节点,再插入根节点,最后插入左节点,实现步骤为:如果栈1的栈顶节点没被访问,则弹出该节点,并将右孩子节点(若有)加入栈中,将该节点加入栈,最后将左孩子节点(若有)加入栈中;同时栈2加入对应的是否被访问的标签。

【代码】

python版本

递归解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def traverse(self, node):
        if not node:
            return
        
        # 左根右
        self.traverse(node.left)
        self.res.append(node.val)
        self.traverse(node.right)
    
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        self.traverse(root)
        return self.res

非递归解法

class Solution:    
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        '''非递归遍历'''
        if not root:
            return []
        stack = [root]
        visit = [0]
        res = []
        while len(stack) > 0:
            # 已经遍历过,将val放到res中
            if visit[-1] == 1:
                res.append(stack.pop().val)
                visit.pop()
            # 未遍历过,则遍历左右节点(由于是栈,先保存右节点,再保存左节点)    
            else:
                node = stack.pop()
                visit_i = visit.pop()
                if node.right:
                    stack.append(node.right)
                    visit.append(0)
                stack.append(node)
                visit.append(1)
                if node.left:
                    stack.append(node.left)
                    visit.append(0)
                
        return res

【相似题目】

144. 二叉树的前序遍历

解题思路:根左右的遍历顺序。

145. 二叉树的后序遍历

解题思路:左右根的遍历顺序。

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群2刷题总结1010——二叉树的层序遍历

    https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

    木又AI帮
  • 打卡群刷题总结0804——二叉树的中序遍历

    非递归解法,需要使用栈结构,同时使用一个visit数组标识该节点是否访问过其孩子节点。得到visit栈顶元素,判断是否访问过;如果访问过,则val加入到结果中;...

    木又AI帮
  • 打卡群刷题总结0808——二叉树的层序遍历

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 打卡群2刷题总结1011——从前序与中序遍历序列构造二叉树

    https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder...

    木又AI帮
  • 打卡群刷题总结0811——从中序与后序遍历序列构造二叉树

    链接:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-posto...

    木又AI帮
  • 打卡群刷题总结0810——从前序与中序遍历序列构造二叉树

    链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inor...

    木又AI帮
  • 打卡群刷题总结0809——二叉树的锯齿形层次遍历

    链接:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal

    木又AI帮
  • 打卡群2刷题总结1012——二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    木又AI帮
  • 打卡群2刷题总结1013——不同的二叉搜索树

    https://leetcode-cn.com/problems/unique-binary-search-trees/

    木又AI帮
  • 打卡群刷题总结0807——验证二叉搜索树

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 【leetcode刷题】T111-二叉树的中序遍历

    木又AI帮
  • leecode刷题(29)-- 二叉树的中序遍历

    希希里之海
  • 打卡群刷题总结0805——不同的二叉搜索树

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 【二叉树打卡4】二叉树的中序遍历(非递归版)

    二叉树的中序遍历顺序是左-根-右。我们可以采用一个栈来辅助,我们把中序遍历的结果放到一个 ArrayList 容器中作为返回值,具体步骤如下:

    帅地
  • 打卡群刷题总结0813——二叉树展开为链表

    链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

    木又AI帮
  • 打卡群刷题总结0814——二叉树展开为链表

    链接:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node

    木又AI帮
  • ​LeetCode刷题实战94:二叉树的中序遍历

    https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

    程序IT圈
  • 本周小结!(二叉树)

    发现大家周末的时候貌似都不在学习状态,周末的文章浏览量和打卡情况照工作日差很多呀,可能是本周日是工作日了,周六得好好放松放松,哈哈,理解理解,但我还不能不更啊,...

    代码随想录
  • 打卡群刷题总结0812——路径总和 II

    链接:https://leetcode-cn.com/problems/path-sum-ii

    木又AI帮

扫码关注云+社区

领取腾讯云代金券