二叉树

二叉树的构建和遍历

python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, data):
        self.data = data
        self.root = self.create(None, 0) # 初始化，构造二叉树
        self.traversal = [] #　用于存放遍历的结果
    
    # 其本身以及左右子树都是二叉树，可以利用递归构造二叉树
    def create(self, root, i): 
        if(i >= len(self.data)):
            return root
        root = TreeNode(self.data[i])
        root.left = self.create(root.left, 2 * i + 1) # 递归建左子树
        root.right = self.create(root.right, 2 * i + 2) # 递归建右子树
        return root # 注意要返回root
    
    # 递归形式的前序遍历（根节点-左子树-右子树）
    def preorder_recur(self, root): 
        if(not root): # 遍历到叶子结点时，直接return
            return
        self.traversal.append(root.val) # 输出
        self.preorder_recur(root.left) # 递归左子树
        self.preorder_recur(root.right) # 递归右子树
    
    # 非递归形式的前序遍历（根节点-左子树-右子树）
    def preorder_unrecur(self, root): 
        stack = [] # 用来记录临时结点
        p = root
        while(stack or p):
            while(p): # 遍历所有的左子结点，依次压入栈中并输出
                self.traversal.append(p.val)
                stack.append(p)
                p = p.left
            p = stack.pop() # 弹出栈顶元素，即为当前根节点最左侧的子结点
            p = p.right # 取其右子结点，继续while循环遍历其右子结点的左子结点，直至全部结点遍历结束
    
    # 递归形式的中序遍历（左子树-根节点-右子树）
    def inorder_recur(self, root): 
        if(not root): # 遍历到叶子结点时，直接return
            return
        self.inorder_recur(root.left) # 递归左子树
        self.traversal.append(root.val) # 输出
        self.inorder_recur(root.right) # 递归右子树
    
    # 非递归形式的中序遍历（左子树-根节点-右子树）
    def inorder_unrecur(self, root): 
        stack = [] # 用来记录临时结点
        p = root
        while(stack or p):
            while(p): # 遍历所有的左子结点，依次压入栈中
                stack.append(p)
                p = p.left
            p = stack.pop() # 弹出栈顶元素，即为当前根节点最左侧的子结点
            self.traversal.append(p.val) # 输出
            p = p.right # 取其右子结点，继续while循环遍历其右子结点的左子结点，直至全部结点遍历结束
    
    # 递归形式的后序遍历（左子树-右子树-根节点）
    def postorder_recur(self, root): 
        if(not root): # 遍历到叶子结点时，直接return
            return
        self.postorder_recur(root.left) # 递归左子树
        self.postorder_recur(root.right) # 递归右子树
        self.traversal.append(root.val) # 输出
    
    # 非递归形式的后序遍历（左子树-右子树-根节点）
    def postorder_unrecur(self, root): 
        # 我们发现，‘左-右-根’其实就是‘根-右-左’的逆序输出
        # 因此我们可以仿照非递归的前序遍历算法，只需修改左右子树的遍历顺序，最后逆序输出即可
        stack = [] # 用来记录临时结点
        p = root
        while(stack or p):
            while(p): # 遍历所有的右子结点，依次压入栈中并输出
                self.traversal.append(p.val)
                stack.append(p)
                p = p.right
            p = stack.pop() # 弹出栈顶元素，即为当前根节点最右侧的子结点
            p = p.left # 取其左子结点，继续while循环遍历其左子结点的右子结点，直至全部结点遍历结束
        # 此时得到的输出为‘根-右-左’，逆序输出即为后序遍历的结果
        self.traversal = self.traversal[::-1]

运行结果

python

bTree = BinaryTree([30, 24, 46, 15, 27, 2, 6, 17, 4, 8, 29]) # 建树

# 递归前序遍历
bTree.traversal = []
bTree.preorder_recur(bTree.root)
print(bTree.traversal)
#非递归前序遍历
bTree.traversal = []
bTree.preorder_unrecur(bTree.root)
print(bTree.traversal)

>>> [30, 24, 15, 17, 4, 27, 8, 29, 46, 2, 6]
>>> [30, 24, 15, 17, 4, 27, 8, 29, 46, 2, 6]

python

# 递归中序遍历
bTree.traversal = []
bTree.inorder_recur(bTree.root)
print(bTree.traversal)
# 非递归中序遍历
bTree.traversal = []
bTree.inorder_unrecur(bTree.root)
print(bTree.traversal)

>>> [17, 15, 4, 24, 8, 27, 29, 30, 2, 46, 6]
>>> [17, 15, 4, 24, 8, 27, 29, 30, 2, 46, 6]

python

# 递归后序遍历
bTree.traversal = []
bTree.postorder_recur(bTree.root)
print(bTree.traversal)
# 非递归后序遍历
bTree.traversal = []
bTree.postorder_unrecur(bTree.root)
print(bTree.traversal)

>>> [17, 4, 15, 8, 29, 27, 24, 2, 6, 46, 30]
>>> [17, 4, 15, 8, 29, 27, 24, 2, 6, 46, 30]

算法题案例

重建二叉树

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解题思路

python

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.traversal = []

    def postorder_recur(self, root): # 后序遍历，用于验证
        if(not root): # 遍历到叶子结点时，直接return
            return
        self.postorder_recur(root.left) # 递归左子树
        self.postorder_recur(root.right) # 递归右子树
        self.traversal.append(root.val) # 输出
        
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        if(not pre or not tin): 
            return None

        root = TreeNode(pre[0]) # 前序遍历中第一个元素即为根节点
        rootIdx = tin.index(root.val) # 找到根节点在中序遍历中的位置

        tinLeft = tin[:rootIdx] # 中序遍历中位于根节点左侧的所有元素即为左子树的中序遍历结果
        preLeft = pre[1:len(tinLeft) + 1] # 根据左子树的大小，取出前序遍历中属于左子树的前序遍历结果
        root.left = self.reConstructBinaryTree(preLeft, tinLeft) # 递归重建左子树

        tinRight = tin[rootIdx + 1:] # 中序遍历中位于根节点右侧的所有元素即为右子树的中序遍历结果
        preRight = pre[len(tinLeft) + 1:] # 前序遍历中剩余部分即为右子树的前序遍历结果
        root.right = self.reConstructBinaryTree(preRight, tinRight) # 递归重建右子树
        return root

运行结果

重建二叉树后，利用前文二叉树的后序遍历算法，进行验证

python

S = Solution()
root = S.reConstructBinaryTree([1,2,4,7,3,5,6,8], [4,7,2,1,5,3,8,6])

S.postorder_recur(root)
print(S.traversal)

>>> [7, 4, 2, 5, 8, 6, 3, 1]

---

二叉树的镜像

题目来源：剑指Offer & Leetcode
题目链接：牛客网-剑指Offer、Leetcode-226
题目描述：

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述：

解题思路

运行结果

---

二叉搜索树与双向链表

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

解题思路

运行结果

---

二叉树的所有路径

题目来源：Leetcode
题目链接：Leetcode-257
题目描述：

给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:

解题思路

运行结果

---

二叉树中和为某一值的路径

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

解题思路

运行结果

---

二叉搜索树的后序遍历序列

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

解题思路

运行结果

---

从上往下打印二叉树

题目来源：剑指Offer & Leetcode
题目链接：牛客网-剑指Offer、Leetcode-102、Leetcode-107
题目描述：

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

解题思路

运行结果

---

平衡二叉树

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

解题思路

运行结果

---

二叉树的深度

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

解题思路

运行结果

---

按之字形顺序打印二叉树

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

解题思路

运行结果

---

对称的二叉树

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

解题思路

运行结果

---

把二叉树打印成多行

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

解题思路

运行结果

---

二叉树的下一个结点

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解题思路

运行结果

---

序列化二叉树

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

解题思路

运行结果

---

二叉搜索树的第k个结点

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

解题思路

运行结果