制作网站如何选择主机,服装网站推广策划书,建设银行余额明细查询,怎么学电商从零开始给定一个二叉树的根节点root,返回它的中序遍历。 方法一#xff1a;递归
二叉树的中序遍历#xff1a;按照访问左子树——根节点——右子树的方式遍历这棵树#xff0c;而在访问左子树或者右子树的时候我们按照同样的方式遍历#xff0c;直到遍历完整棵树。因此整个遍历过…给定一个二叉树的根节点root,返回它的中序遍历。 方法一递归
二叉树的中序遍历按照访问左子树——根节点——右子树的方式遍历这棵树而在访问左子树或者右子树的时候我们按照同样的方式遍历直到遍历完整棵树。因此整个遍历过程天然具有递归的性质
运行过程 从根节点 1 开始 递归遍历左子树1 的左子树为空直接返回。 将 1 的值添加到结果列表 res 中res [1]。 递归遍历右子树1 的右子树是 2。 进入节点 2 递归遍历左子树2 的左子树是 3。 进入节点 3 递归遍历左子树3 的左子树为空直接返回。 将 3 的值添加到结果列表 res 中res [1, 3]。 递归遍历右子树3 的右子树为空直接返回。 将 2 的值添加到结果列表 res 中res [1, 3, 2]。 递归遍历右子树2 的右子树为空直接返回。 遍历结束返回结果 res [1, 3, 2]
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def inorderTraversal(self, root)::type root: Optional[TreeNode]:rtype: List[int]res[] #存储遍历结果self.inorder(root,res) #中序遍历return resdef inorder(self,root,res): #递归函数用于实现中序遍历if not root: #如果当前节点 root 为空直接返回return self.inorder(root.left,res)res.append(root.val) #将当前节点的值 root.val 添加到结果列表 res 中self.inorder(root.right,res)
时间复杂度O(n)n为二叉树节点的个数
空间复杂度O(n) 方法二迭代 # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def inorderTraversal(self, root)::type root: Optional[TreeNode]:rtype: List[int]res[] #空列表用于存储遍历结果stack[] #空列表用作栈来辅助遍历while root or stack: #当 root 不为空或栈 stk 不为空时继续循环while root: #当root不为空时将root推入栈stk中stack.append(root) #将 root 移动到其左子节点rootroot.left #将当前节点的所有左子节点推入栈中直到到达最左侧的节点rootstack.pop() #从栈 stk 中弹出栈顶节点赋值给 root,当前子树的最左侧节点res.append(root.val) #将当前节点 root 的值 root.val 添加到结果列表 res 中rootroot.right #将 root 移动到其右子节点return res
时间复杂度O(n)
空间复杂度O(n) 方法三Morris中序遍历
Morris 遍历算法是另一种遍历二叉树的方法它能将非递归的中序遍历空间复杂度降为O(1)。
Morris 遍历算法整体步骤如下假设当前遍历到的节点为x
1.如果x无左孩子先将x的值加入答案数组再访问x的右孩子即xx.right
2.如果x有左孩子则找到x左子树上最右的节点即左子树中序遍历的最后一个节点x,x在中序遍历中的前驱节点记为predecessor。根据predecessor的右孩子是否为空进行如下操作:
如果predecessor的右孩子为空则将其右孩子指向x然后访问x的左孩子即xx.left。
如果predecessor的右孩子不为空则此时其右孩子指向x说明已经遍历完x的左子树将predecessor的右孩子置空将x的值加入答案数组然后访问x的右孩子即xx.right。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def inorderTraversal(self, root)::type root: Optional[TreeNode]:rtype: List[int]res[] #列表用来存储最终的中序遍历结果predcessorNone #当前节点的前驱节点即当前节点的左子树中最右边的节点while root: #只要当前节点不为空就继续遍历if root.left:predcessorroot.left #predecessor 节点就是当前 root 节点向左走一步然后一直向右走至无法走为止while predcessor.right and predcessor.right ! root:predcessorpredcessor.rightif predcessor.right is None: #predecessor 的右指针指向 root继续遍历左子树predcessor.rightroot #前驱节点的右子树为空把它的右子树指向当前节点 rootrootroot.left #移动到它的左子树继续遍历else:#前驱节点的右子树指向了当前节点说明左子树遍历完成可以访问当前节点res.append(root.val)predcessor.rightNone rootroot.rightelse:#当前节点没有左子树直接访问当前节点并将 root 移动到右子树res.append(root.val)rootroot.rightreturn res
时间复杂度O(n)
空间复杂度O(1)
