二叉树总结

一、题目列表：

题目1、二叉树的深度
题目2、二叉搜索树的第k个节点
题目3、二叉树镜像
题目4、从上往下打印二叉树
题目5、二叉树中和为某一值的路径(一)
题目6、重建二叉树 JZ7
题目7、二叉树的下一个结点 JZ8
题目8、树的子结构 JZ26

定义：

1.二叉树遍历

二叉树的遍历分为两种方式：深度优先算法、广度优先算法(又叫层次遍历)

(1)深度优先算法

• 有三种方式：前序遍历、中序遍历、后序遍历
• 有两种算法可以实现三种遍历：递归和迭代(非递归)
• 【备注】：二叉树的深度优先遍历的非递归的通用做法是采用栈

(2)广度优先算法

• 有两种算法可以实现遍历：递归和迭代(非递归)
• 广度优先遍历的非递归的通用做法是采用队列

二.实现代码

1.深度优先算法

• 有三种方式：前序遍历、中序遍历、后序遍历
• 有两种算法可以实现三种遍历：递归和迭代(非递归)

#先创建二叉树
#!/usr/bin/python
class node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
root = node(5)
root.left = node(7)
root.right = node(8)
root.left.left = node(3)
root.left.right = node(4)
root.left.right.left = node(9)

#递归实现-前序遍历：
def preoder(root):                                                      
    if root is None:                                                            
        return                                                                  
    else:                                                                                                                                  
        print (root.val)                                                     
        preoder(root.left)                          
        preoder(root.right) 
      
#递归实现-中序遍历：
def minoder(root):                                                      
    if root is None:                                                            
        return                                                                  
    else:                                                                                                                                                                                    
        minoder(root.left) 
        print (root.val)                          
        minoder(root.right)       

#递归实现-后序遍历：
def postoder(root):                                                      
    if root is None:                                                            
        return                                                                  
    else:                                                                                                                                                                                    
        postoder(root.left)                
        postoder(root.right) 
        print (root.val)  


#迭代实现-前序遍历：
stack = [root]
result = [] 
while stack:
    t = stack.pop()
    if type(t) is node:
        stack.extend([t.right,t.left,t.val]) #只改变顺序就能实现前中后序遍历
    else:
        if t:
            result.append(t)
print(result)

#迭代实现-中序遍历：
stack = [root]
result = [] 
while stack:
    t = stack.pop()
    if type(t) is node:
        stack.extend([t.right,t.val,t.left])
    else:
        if t:
            result.append(t)
print(result)

#迭代实现-后序遍历：
stack = [root]
result = [] 
while stack:
    t = stack.pop()
    if type(t) is node:
        stack.extend([t.val,t.right,t.left])
    else:
        if t:
            result.append(t)
print(result)

2、广度优先算法

第一种：
def breadth_trav(root):
    if root is None:
        return
    queue = [root]
    while queue:
        cur_node = queue.pop(0)
        print(cur_node.val)
        if cur_node.left:
            queue.append(cur_node.left)
        if cur_node.right:
            queue.append(cur_node.right)

第二种：稍微变形
def TreeDepth( pRoot):
    if not pRoot:
        return 0
    qu = [pRoot]
    while(qu):
        tmp = []
        for i in qu:
            print(i.val)
            if i.left:
                tmp.append(i.left)
            if i.right:
                tmp.append(i.right)
        qu = tmp

二、题目

题目1、二叉树的深度

1.整体思路

方法一、递归
时间复杂度：O(n)O(n)O(n)，其中nnn为二叉树的节点数，遍历整棵二叉树
空间复杂度：O(n)O(n)O(n)，最坏情况下，二叉树化为链表，递归栈深度最大为nnn
方法二、层次遍历
时间复杂度：O(n)O(n)O(n)，其中nnn为二叉树的节点数，遍历整棵二叉树
空间复杂度：O(n)O(n)O(n)，最坏情况下，二叉树化为链表，递归栈深度最大为nnn

2.代码

方法一：递归
class Solution:
    def TreeDepth(self , pRoot: TreeNode) -> int:
        # write code here
        if not pRoot:
            return 0
        return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right)) +1


方法二：层次遍历

class Solution:
    def TreeDepth(self , pRoot: TreeNode) -> int:
        # write code here
        if not pRoot:
            return 0
        qu = [pRoot]
        num = 0
        while(qu):
            tmp = []
            for i in qu:
                if i.left:
                    tmp.append(i.left)
                if i.right:
                    tmp.append(i.right)
            qu = tmp
            num +=1
        return num

题目2、二叉搜索树的第k个节点

来源：剑指offer第54题

1.整体思路

主要考点为：中序遍历
方法一、递归

2.代码

方法二：递归1
class Solution:
    def __init__(self):
        self.nodelist = []
    def result(self,root):
        if not root:
            return []
        self.result(root.left)
        self.nodelist.append(root.val)
        self.result(root.right)
        
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # write code here
        self.result(proot)
        if not proot or k>len(self.nodelist) or k<=0:
            return -1
        return self.nodelist[k-1]


方法一：递归2
class Solution:
    def result(self,root):
        return self.result(root.left) + [root.val]+ self.result(root.right) if root else []
      
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # write code here
        re = self.result(proot)
        if not proot or k>len(re) or k<=0:
            return -1
        return re[k-1]

题目3、二叉树镜像

来源：剑指offer第27题
操作给定的二叉树，将其变换为源二叉树的镜像。
原二叉树：

镜像：

1.整体思路

主要考点为：层序遍历，
层序遍历每一层，让后让左右子节点换位置

2.代码

class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        if not pRoot:
            return None
        qu = [pRoot]
        while(qu):
            node = qu.pop(0)
            if node.left:
                qu.append(node.left)
            if node.right:
                qu.append(node.right)
            tmp = node.left
            node.left = node.right
            node.right = tmp
        return pRoot

题目4、从上往下打印二叉树

来源：剑指offer第32题

1.整体思路

主要考点为：层序遍历

2.代码

class Solution:
    def PrintFromTopToBottom(self , pRoot: TreeNode) -> List[int]:
        # write code here
        if not pRoot:
            return None
        result = []
        qu = [pRoot]
        while(qu):
            node = qu.pop(0)
            result.append(node.val)
            if node.left:
                qu.append(node.left)
            if node.right:
                qu.append(node.right)
        return result

题目5、二叉树中和为某一值的路径(一)

来源：剑指offer第82题
描述：
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n

1.整体思路

主要考点为：层序遍历

2.代码

class Solution:
    def hasPathSum(self , root: TreeNode, sum: int) -> bool:
        # write code here
        if not root:
            return False
        qu = [root]
        while qu:
            node = qu.pop()
            if not node.left and not node.right and node.val ==sum:
                return True
            if node.left:
                node.left.val = node.left.val + node.val
                qu.append(node.left)
            if node.right:
                node.right.val = node.right.val + node.val
                qu.append(node.right)   
        return False

题目6、重建二叉树 JZ7

来源：剑指offer第7题
描述：
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

1.整体思路

1.先找根节点位置，根据根节点位置可以把前序遍历序列和和中序遍历序列分出来左树和右树
2.分别递归重建左树和右树

2.代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pre int整型一维数组 
# @param vin int整型一维数组 
# @return TreeNode类
#
class Solution:
    def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
        # write code here
        if not pre:
            return None
        root = TreeNode(pre[0])
        mind = vin.index(root.val) #找到根节点的位置，
        root.left = self.reConstructBinaryTree(pre[1:mind+1],vin[:mind])
        root.right = self.reConstructBinaryTree(pre[mind+1:],vin[mind+1:])
        return root

题目7、二叉树的下一个节点

来源：剑指offer第8题
描述：
给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

1.整体思路

2.代码

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def __init__(self):
        self.flag = None
        self.result = None
        self.nodes = []
    def GetNext(self, pNode):
        # 设置根节点占位符
        root = pNode
        self.flag = pNode
        #先找到根节点
        while root.next:
            root = root.next
        # 中序遍历
        self.InOrder(root)
        # 返回最终结果
        return self.result
            
    # 中序遍历
    def InOrder(self, root):
        if root == None:
            return
        self.InOrder(root.left)
        if self.nodes and self.nodes[-1] ==self.flag:
            self.result = root
        self.nodes.append(root)
        self.InOrder(root.right)     

题目8、树的子结构 JZ26
来源：剑指offer第26题
描述：
输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

1.整体思路

2.代码

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if pRoot1 == None:
            return False
        if pRoot2 == None:
            return False
        if self.is_subtree(pRoot1,pRoot2):
            return True
        if self.HasSubtree(pRoot1.left,pRoot2):
            return True
        if self.HasSubtree(pRoot1.right,pRoot2):
            return True
        
    def is_subtree(self,A,B):
        if B == None:
            return True
        if A == None:
            return False
        if A.val == B.val:
            return self.is_subtree(A.left,B.left) and self.is_subtree(A.right, B.right)
        else:
            return False