分类 二叉树 下的文章

一、定义：

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