Hexo

###思路

首先题目的要求是原地

• 首先判断是否有root,如果没有则return空值
• 接下来将root.left二叉树复制给node，然后开始判断是否有if node,有的话继续判断该节点是否有右子节点while node.right:,如果有右子节点就继续判断node=node.right。
• 将根节点的右子节点复制到，刚刚搜索到的那个节点的右子节点node.right=root.right。
• 将整个根节点的左子节点覆盖根节点的右子节点root.right=root.left，并将根节点的左子节点重置为None
• 最后递归调用，参数为根节点的右子节点root.right，也就是现在root.right作为新的root根节点，之后的每次递归调用都更新根节点。

###具体代码以及注释如下：

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """       
        if not root:
            return
        # 后序遍历
        self.flatten(root.left)
        self.flatten(root.right)
        if root.left and root.right:
            # 寻找root.left尾部用的指针
            index = root.left
            # while循环找root.left的尾部
            while index.right:
                index=index.right
            # 进行拼接工作
            index.right = root.right
            root.right=root.left
            root.left=None
            # 如果没有左节点，就不用拼接了
        elif not root.right and root.left:
            root.right=root.left
            root.left=None

1.前序遍历

前序遍历执行的是中左右的遍历原则，即先遍历中间的根节点，然后左节点，最后右节点。这样获得的遍历顺序为：1245367

def preorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        tree.append(node.val)
        helper(node.left)
        helper(node.right)
    helper(root)
    return tree

2.中序遍历

def innerorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        helper(node.left)
        tree.append(node.val)
        helper(node.right)
    helper(root)
    return tree

3.后序遍历

后序遍历执行的是左右中的遍历原则，即先遍历中间的左节点，然后右节点，最后中节点。

def postorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        helper(node.left)
        helper(node.right)
        tree.append(node.val)
    helper(root)
    return tree

4.总结规律

基于以上代码可见，二叉树的遍历基本的代码框架如下：

def Traversal(root):
    tree = []
    def helper(node):
        #判断当前节点是否为空
        #执行当前节点操作
        #执行左右子树操作
    helper(root)
    return tree

1

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦