07-13：二叉树review1

二叉树review1:

1、二叉树结构

1）二叉树的遍历

0）递归/迭代实现 前/中/后序遍历

递归

迭代

层次遍历 -> 二叉树深度

之字遍历 ：关键是有标识位

1）输出二叉树的右视图

迭代：每一行保存，打印每一行最后一个元素

递归：关键是有个层数的标志位

层数小于加入节点数，加入当前节点

           if not root:

               return

            if level>len(path):

               path.append(root.val)

            rightsideview(root.right,level+1,path)

            rightsideview(root.left,level+1,path)

2）平衡二叉树

判断直径和子树

3）搜索二叉树

中序遍历是否升序

4）完全二叉树

最后一层从没有子节点开始，后面都没有子节点

5）二叉树的对称

讲根节点看作两个节点，左右节点值是否相等以及左的左和右的右，左的右和右的左是否满足相等。

6）二叉树的镜像

递归后左右节点交换

7）判断t1中是否存在和t2相同的子结构

关键先写一个判断相同的函数，再判断根->左/右节点

8）序列化

按先序遍历访问，按同样的顺序还原。

访问顺序可选层序遍历。

def Serialize(self, root):

        # write code here

        res=[]

        queue=[root]

        while len(queue)>0:

            tmp=queue.pop(0)

            if tmp:

                res.append(str(tmp.val))

                queue.append(tmp.left)

                queue.append(tmp.right)

            else:

                res.append('x')

        return ','.join(res)

    def Deserialize(self, s):

        if (s == 'x'):

            return None

        # write code here

        lists=s.split(',')

        root=TreeNode(int(lists[0]))

        queue=[root]

        cur=1

        while cur<len(lists):

            node=queue.pop(0)

            leftval=lists[cur]

            rightval=lists[cur+1]

            if leftval!='x':

                leftnode=TreeNode(int(leftval))

                node.left=leftnode

                queue.append(leftnode)

            if rightval!='x':

                rightnode=TreeNode(int(rightval))

                node.right=rightnode

                queue.append(rightnode)

            cur=cur+2

        return root

https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=117&&tqId=37782&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking

2、路径和