牛客网---二叉树（python实现）

谁践踏了优雅 2022-11-05 08:37 133阅读 0赞

### 王霸之气 ###

*   *   *  一：重建二叉树：
         *  二：判断二叉树是否对称（镜像二叉树）：
         *  三：转换成镜像二叉树：
         *  四：寻找根节点到叶子节点的和等于SUM的路径是否存在：
         *  五：寻找根节点到叶子节点的和等于SUM的路径，并输出路径：
         *  六：二叉树层序遍历：
         *  七： 二叉树之字形层序遍历：
         *  八：寻找两个节点最近的公共祖先：
         *  九：二叉树的最大深度：
         *  十：平衡二叉树：
         *  十一：二叉搜索树的第K个结点：
         *  十二：合并二叉树：
         *  十三：有序数组转化成平衡二叉搜索树：
         *  十四：完全二叉树的节点数：

### 一：重建二叉树： ###

题目要求: 输入先序遍历和中序遍历，构建二叉树并返回。  
思路：  
**递归创建， 每次将先序遍历的根节点取出来，作为当前节点， 然后左子树节点和右子树节点可以递归生成。**  
**递归边界是什么？当传递进来的先序遍历或者中序遍历零个结点的时候，说明这个结点是叶子节点。**  
**左递归的时候，先序遍历需要如何传递参数？**  
答：**左递归应该传递的是左子树的所有元素，对于先序遍历则是初始元素的下一个到，中序遍历的位置（包括中序遍历）对于中序遍历，则是从开始到中间位置左边的那一个位置。**

class Solution:
        # 返回构造的TreeNode根节点
        def reConstructBinaryTree(self, pre, tin):
            # 1:递归边界：如果中序/先序另个元素，说明是叶子节点
            if len(pre) == 0:
                return None
            # 2：创建根节点
            node = TreeNode(pre[0])
            # 3: 根节点在中序遍历中的位置
            pos = tin.index(pre[0])
            # 4: 左节点递归和右节点递归
            node.left = self.reConstructBinaryTree(pre[1:pos+1], tin[:pos])
            node.right = self.reConstructBinaryTree(pre[pos+1:], tin[pos+1:])
            return node

### 二：判断二叉树是否对称（镜像二叉树）： ###

思路：递归的思想：  
一： 递归的边界？  
**答： 我们在递归到两片叶子结点的时候， 如果都是叶子则说明是对称的，返回是True, 如果其中任何一个不是叶子节点，则肯定不是对称的，直接返回False。**  
二： 递归的一般情况：  
**答： 对于不是叶子节点的两个中间结点，我们肯定要保证三点：1：两个节点的值相等。2：A的左子树=B的右子树。 3： A的右子树 = B 的左子树。**

class Solution:
        
        def shanwen(self, l1, l2):
            if l1 == None and l2 == None:
                return True
            elif l1 == None:
                return False
            elif l2 == None:
                return False
            else:
                return l1.val == l2.val and self.shanwen(l1.left, l2.right) and self.shanwen(l1.right, l2.left)
            
        
        def isSymmetric(self , root ):
            if not root:
                return True
            return self.shanwen(root.left, root.right)

### 三：转换成镜像二叉树： ###

思路： 递归实现  
**递归边界：如果传递的root是None，说明不是树的节点，则直接return  
然后交换左右节点，进行左递归和右递归。最终return总的节点。**

class Solution:
        def Mirror(self , pRoot ):
            if pRoot == None:
                return 
            temp_root = TreeNode(0)
            temp_root = pRoot.left
            pRoot.left = pRoot.right
            pRoot.right = temp_root
            self.Mirror(pRoot.left)
            self.Mirror(pRoot.right)
            return pRoot

### 四：寻找根节点到叶子节点的和等于SUM的路径是否存在： ###

思路：递归实现：  
**递归边界： 特殊情况： 如果开始是个空节点，则直接返回False。边界是到达叶子节点的时候，我们判断sum-叶子值是否是0。如果是0,则返回True,如果不是返回False。  
一般情况： 只要左边递归或者右边递归一个是True,则就可以返回True。**

class Solution:
        def hasPathSum(self , root , sum ):
            if root == None:
                return False
            if root.left == None and root.right == None:
                if sum - root.val == 0:
                    return True
                else:
                    return False
            return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

### 五：寻找根节点到叶子节点的和等于SUM的路径，并输出路径： ###

思路：

class Solution:
        def pathSum(self , root , sum ):
            res = []
            # 1: 特殊情况： 如果是空节点则直接返回None
            if root is None:
                return res
            # 2: 定义内层函数
            def Path(root, sum, tmp):
                # 如果递归到最后，返回None
                if root is None:
                    return
                # 将当前节点的值加入进入
                tmp_ = tmp + [root.val]
                # sum的值减少
                sum = sum - root.val
                # 判断是否是叶子结点
                if sum == 0 and root.left is None and root.right is None:
                    # 如果是，将字典追加进去
                    res.append(tmp_)
                    return
                # 如果不是则继续递归。
                if root.left is not None:
                    Path(root.left, sum, tmp_)
                if root.right is not None:
                    Path(root.right, sum, tmp_)
                return
            # 3：调用内层函数，传递一个空字典
            Path(root, sum, [])
            return res

### 六：二叉树层序遍历： ###

思路：

class Solution:
        def levelOrder(self , root ):
            if not root:
                return []
            res = [] # 保存返回的数据
            queue = [root] # 创建队列
            while queue:
                level = []
                for i in range(len(queue)): # 队列中的子元素都是在一行中的
                    temp = queue.pop(0)
                    level.append(temp.val) # 追加这层的值
                    if temp.left:
                        queue.append(temp.left)
                    if temp.right:
                        queue.append(temp.right)
                res.append(level)
            return res

### 七： 二叉树之字形层序遍历： ###

思路：

class Solution:
        def zigzagLevelOrder(self , root ):
            if not root:
                return []
            res = [] # 保存返回的数据
            queue = [root] # 创建队列
            flag = 1
            while queue:
                level = []
                for i in range(len(queue)): # 队列中的子元素都是在一行中的
                    temp = queue.pop(0)
                    level.append(temp.val) # 追加这层的值
                    if temp.left:
                        queue.append(temp.left)
                    if temp.right:
                        queue.append(temp.right)
                if flag % 2 != 0:
                    res.append(level)
                    flag += 1
                else:
                    res.append(level[::-1])
                    flag += 1
            return res

### 八：寻找两个节点最近的公共祖先： ###

思路：

class Solution:
        def lowestCommonAncestor(self , root , o1, o2 ):
            if not root:
                return None
            if root.val == o1 or root.val == o2:
                return root.val
            left = self.lowestCommonAncestor(root.left, o1, o2)
            right = self.lowestCommonAncestor(root.right, o1, o2)
            if left and right:
                return root.val
            if left:
                return left
            if right:
                return right
            return None

### 九：二叉树的最大深度： ###

class Solution:
        def maxDepth(self , root ):
            # 1: 如果是空节点，则直接返回0
            if root == None:
                return 0
            return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

### 十：平衡二叉树： ###

平衡二叉树（Balanced Binary Tree），具有以下性质：**它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。**  
思路：

class Solution:
        
        def height(self, root):
            if (root == None):
                return 0
            return max(self.height(root.left), self.height(root.right)) + 1
        
        def IsBalanced_Solution(self, pRoot):
            # 1: 特殊情况：如果是个空树则直接返回True,递归到最后叶子以下，也要返回True
            if pRoot == None:
                return True
            # 2: 如果左面是平衡二叉树，右面也是平衡二叉树，并且两个高度相差小于等于1，则返回true
            if self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right) and ((self.height(pRoot.left) - self.height(pRoot.right)) in [-1, 0, 1]):
                return True
            else:
                return False

### 十一：二叉搜索树的第K个结点： ###

二叉搜索树的特点：**左子树小于根节点，右子树大于根节点**。  
思路： **中序遍历一遍二叉搜索树，然后将节点全部存储到一个数组中，最后返回数组中下标为K-1的即可。**

class Solution:
        # 中序遍历
        def mid(self, root, result):
            if root:
                self.mid(root.left, result)
                result.append(root)
                self.mid(root.right, result)
            return result
        
        def KthNode(self, pRoot, k):
            if not pRoot:
                return None
            result = self.mid(pRoot, [])
            if k>len(result) or k <=0:
                return None
            return result[k-1]

### 十二：合并二叉树： ###

要求：**都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替**。

class Solution:
        
        def mergeTrees(self , t1 , t2 ):
            if t1 == None and t2 == None:
                return None
            elif t1 == None and t2 != None:
                return t2
            elif t1 != None and t2 == None:
                return t1
            else:
                t1.val += t2.val
                t1.left = self.mergeTrees(t1.left, t2.left)
                t1.right = self.mergeTrees(t1.right, t2.right)
                return t1

### 十三：有序数组转化成平衡二叉搜索树： ###

平衡二叉搜索树：**左子树小于根节点，右子树大于根节点，左子树和右子树高相差不到1**。  
思路：  
这道题是要将有序数组转为二叉搜索树，所谓二叉搜索树，是一种始终满足左<根<右的特性，如果将二叉搜索树按中序遍历的话，得到的就是一个有序数组了。那么反过来，**我们可以得知，根节点应该是有序数组的中间点，从中间点分开为左右两个有序数组，在分别找出其中间点作为原中间点的左右两个子节点，这不就是是二分查找法的核心思想么。所以这道题考的就是二分查找法。**

class Solution:
        def sortedArrayToBST(self , num ):
            length = len(num)
            mid = length // 2
            if length == 0:
                return None
            root = TreeNode(num[mid])
            root.left = self.sortedArrayToBST(num[:mid])
            root.right = self.sortedArrayToBST(num[mid + 1:])
            return root

### 十四：完全二叉树的节点数： ###

给定一棵完全二叉树的头节点head，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。  
思路：

class Solution:
        def nodeNum(self , head ):
            if head == None:
                return 0
            return 1 + self.nodeNum(head.left) + self.nodeNum(head.right)

这种方法是递归遍历了一遍，时间和空间复杂度都是O(N)，不太符合题目要求。