文章目录
一，填充每个节点的下一个右侧节点指针
1，程序简介
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
- 输入：root = [1,2,3,4,5,6,7]
- 输出：[1,#,2,3,#,4,5,6,7,#]
- 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，’#’ 标志着每一层的结束。
提示：
- 树中节点的数量少于 4096
- -1000 <= node.val <= 1000
2，程序代码
在这里插入代码片
3，运行结果
二，从中序与后序遍历序列构造二叉树
1，程序简介
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
- 你可以假设树中没有重复的元素。
例如，给出
- 中序遍历 inorder = [9,3,15,20,7]
- 后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
2，程序代码
# -*- coding: utf-8 -*-
"""
Created on Wed Feb 2 15:34:54 2022
Function: 从中序与后序遍历序列构造二叉树
@author: 小梁aixj
"""
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
def build_tree(in_left, in_right, post_left, post_right):
if in_left > in_right:
return
post_root = post_right
root = TreeNode(postorder[post_root])
in_root = inorder_map[root.val]
size_of_left = in_root - in_left
root.left = build_tree(
in_left, in_root - 1, post_left, post_left + size_of_left - 1
)
root.right = build_tree(
in_root + 1, in_right, post_left + size_of_left, post_root - 1
)
return root
size = len(inorder)
inorder_map = {}
for i in range(size):
inorder_map[inorder[i]] = i
return build_tree(0, size - 1, 0, size - 1)
三，删除排序链表中的重复元素
1，程序简介
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。
示例 1：
- 输入：head = [1,1,2]
- 输出：[1,2]
示例 2：
- 输入：head = [1,1,2,3,3]
- 输出：[1,2,3]
提示：
- 链表中节点数目在范围 [0, 300] 内
- -100 <= Node.val <= 100
- 题目数据保证链表已经按升序排列
2，程序代码
# -*- coding: utf-8 -*-
"""
Created on Wed Feb 2 15:35:09 2022
Function: 删除排序链表中的重复元素
@author: 小梁aixj
"""
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class LinkList:
def __init__(self):
self.head=None
def initList(self, data):
self.head = ListNode(data[0])
r=self.head
p = self.head
for i in data[1:]:
node = ListNode(i)
p.next = node
p = p.next
return r
def convert_list(self,head):
ret = []
if head == None:
return
node = head
while node != None:
ret.append(node.val)
node = node.next
return ret
class Solution(object):
def deleteDuplicates(self, head):
if head is None:
return None
pos = head
while pos is not None and pos.next is not None:
if pos.val == pos.next.val:
pos.next = pos.next.next
else:
pos = pos.next
return head
# %%
l = LinkList()
list1 = [1,1,2]
l1 = l.initList(list1)
s = Solution()
print(l.convert_list(s.deleteDuplicates(l1)))