day23|二叉树9-二叉搜索树剪枝、建立、转化成累加树_二叉树遍历剪枝

108.将有序数组转换为二叉搜索树

整体思路： 选择中间结点，将区间分成左区间和右区间，然后依次遍历两种区间，分别作为父节点的左子树和右子树。

# 在递归的思想中，利用遍历左右子树的方式，一步一步按照逻辑进行求解，先找到中间结点的位置，再以中间结点为目标建立左右子树，最终的返回值是当前根节点的值，
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # 每次返回中间结点
        # 注意定义区间：左闭右闭区间
        def createTree(nums,left,right): # 定义非法区间
            if left > right:
                return None
            index = (left+right)//2 # 0
            # 构造完区间之后进行二叉树的构建
            root = TreeNode(val=nums[index])
            # 将左右区间构造的子树返回给上一层结点
            leftIndex1,leftIndex2 = left,index-1 # 0,0
            rightIndex1,rightIndex2 = index+1,right # 1,1
            root.left = createTree(nums,leftIndex1,leftIndex2)
            root.right = createTree(nums,rightIndex1,rightIndex2)
            return root # 构造完各个部分之后，返回相应的子树
        root = createTree(nums,0,len(nums)-1)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

538.把二叉搜索树转换为累加树

双指针： 将上一个结点的数值记为pre，当前结点的数值记为cur
基本思路： 按照遍历的顺序，依次处理右中左三处结点，用pre记录上一个节点数值，
反思： 其实二叉树题目的基本思路是

int pre=0
void traversal(TreeNode* cur){
	if(cur==NULL) return
	traversal(cur.right)
	cur.val += pre
	pre = cur.val
	traversal(cur.left)
}
1
2
3
4
5
6
7
8

递归法

class Solution:
    def __init__(self):
        self.pre = 0
    def traversal(self,root): # 不需要有返回值，只需要更改结点的值即可
        if not root:
            return
        self.traversal(root.right)
        root.val += self.pre
        self.pre = root.val
        self.traversal(root.left)
    
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 右中左的顺序
        self.traversal(root)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

迭代法

利用栈的思想进行求解 ，先将右结点依次入栈，然后再依次将右结点依次进行出栈判断。只要while循环内的条件不为空，就进入相应的循环中。

    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        stack = []
        pre = 0
        cur = root
        while cur or stack:
            # 如果cur存在那么一直往下遍历右结点
            if cur:
                stack.append(cur)
                cur = cur.right
            else:
            	# 如果节点不存在说明走到头了，需要将结点进行弹出操作，然后将其相加再访问左结点。
                top = stack.pop()
                # stack.pop()
                top.val += pre
                pre = top.val
                cur = top.left
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结篇

本章节的内容选自代码随想录

二叉树的种类、存储方式、遍历方式、定义方式

二叉树的遍历方式

深度优先遍历
二叉树：前中后序递归法 (opens new window)：递归三部曲初次亮相
二叉树：前中后序迭代法（一） (opens new window)：通过栈模拟递归
二叉树：前中后序迭代法（二）统一风格(opens new window)
广度优先遍历
二叉树的层序遍历 (opens new window)：通过队列模拟

求二叉树的属性

二叉树：是否对称(opens new window)
递归：后序，比较的是根节点的左子树与右子树是不是相互翻转
迭代：使用队列/栈将两个节点顺序放入容器中进行比较
二叉树：求最大深度(opens new window)
递归：后序，求根节点最大高度就是最大深度，通过递归函数的返回值做计算树的高度
迭代：层序遍历
二叉树：求最小深度(opens new window)
递归：后序，求根节点最小高度就是最小深度，注意最小深度的定义
迭代：层序遍历
二叉树：求有多少个节点(opens new window)
递归：后序，通过递归函数的返回值计算节点数量
迭代：层序遍历
二叉树：是否平衡(opens new window)
递归：后序，注意后序求高度和前序求深度，递归过程判断高度差
迭代：效率很低，不推荐
二叉树：找所有路径(opens new window)
递归：前序，方便让父节点指向子节点，涉及回溯处理根节点到叶子的所有路径
迭代：一个栈模拟递归，一个栈来存放对应的遍历路径
二叉树：递归中如何隐藏着回溯(opens new window)
详解二叉树：找所有路径 (opens new window)中递归如何隐藏着回溯
二叉树：求左叶子之和(opens new window)
递归：后序，必须三层约束条件，才能判断是否是左叶子。
迭代：直接模拟后序遍历
二叉树：求左下角的值(opens new window)
递归：顺序无所谓，优先左孩子搜索，同时找深度最大的叶子节点。
迭代：层序遍历找最后一行最左边
二叉树：求路径总和(opens new window)
递归：顺序无所谓，递归函数返回值为bool类型是为了搜索一条边，没有返回值是搜索整棵树。
迭代：栈里元素不仅要记录节点指针，还要记录从头结点到该节点的路径数值总和

二叉树的修改与构造

翻转二叉树(opens new window)
递归：前序，交换左右孩子
迭代：直接模拟前序遍历
构造二叉树(opens new window)
递归：前序，重点在于找分割点，分左右区间构造
迭代：比较复杂，意义不大
构造最大的二叉树(opens new window)
递归：前序，分割点为数组最大值，分左右区间构造
迭代：比较复杂，意义不大
合并两个二叉树(opens new window)
递归：前序，同时操作两个树的节点，注意合并的规则
迭代：使用队列，类似层序遍历

求二叉搜索树的属性

二叉搜索树中的搜索(opens new window)

递归：二叉搜索树的递归是有方向的
迭代：因为有方向，所以迭代法很简单
是不是二叉搜索树(opens new window)

递归：中序，相当于变成了判断一个序列是不是递增的
迭代：模拟中序，逻辑相同
求二叉搜索树的最小绝对差(opens new window)

递归：中序，双指针操作
迭代：模拟中序，逻辑相同
求二叉搜索树的众数(opens new window)

递归：中序，清空结果集的技巧，遍历一遍便可求众数集合

二叉搜索树转成累加树(opens new window)

递归：中序，双指针操作累加
迭代：模拟中序，逻辑相同

二叉树公共祖先问题

二叉树的公共祖先问题(opens new window)
递归：后序，回溯，找到左子树出现目标值，右子树节点目标值的节点。
迭代：不适合模拟回溯
二叉搜索树的公共祖先问题(opens new window)
递归：顺序无所谓，如果节点的数值在目标区间就是最近公共祖先
迭代：按序遍历
#二叉搜索树的修改与构造
二叉搜索树中的插入操作(opens new window)
递归：顺序无所谓，通过递归函数返回值添加节点
迭代：按序遍历，需要记录插入父节点，这样才能做插入操作
二叉搜索树中的删除操作(opens new window)
递归：前序，想清楚删除非叶子节点的情况
迭代：有序遍历，较复杂
修剪二叉搜索树(opens new window)
递归：前序，通过递归函数返回值删除节点
迭代：有序遍历，较复杂
构造二叉搜索树(opens new window)
递归：前序，数组中间节点分割
迭代：较复杂，通过三个队列来模拟

最后总结

涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。

求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。

求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。

注意在普通二叉树的属性中，我用的是一般为后序，例如单纯求深度就用前序，二叉树：找所有路径 (opens new window)也用了前序，这是为了方便让父节点指向子节点。

所以求普通二叉树的属性还是要具体问题具体分析。