python二叉搜索树建立_二叉搜索树--LeetCode(python)

几种遍历方式：

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:

2

/ \

1   3

输出: true

示例 2:

输入:

5

/ \

1   4

/ \

3   6

输出: false

解释: 输入为: [5,1,4,null,null,3,6]。

根节点的值为 5 ，但是其右子节点值为 4 。

解法

一开始想的是直接和左右值比较，但是忽略了隔层之间可能存在不符合规定的可能性，代码是错的。最后参考了别人的代码，发现别人是从上往下比较的，将每个节点往左就是最大，往右就是最小值，太机智了。还有就是在传输过程中原函数不能够传递最大最小值，又重新定义了一个函数调用遍历方法：使用中序遍历，基本上所有二叉搜索树的操作都可以这样做

解法一：

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

def validBST(self,root,small,large):

if root==None:

return True

if small>=root.val or large<=root.val:

return False

return self.validBST(root.left,small,root.val) and self.validBST(root.right,root.val,large)

def isValidBST(self, root):

"""

:type root: TreeNode

:rtype: bool

"""

return self.validBST(root,-2**32,2**32-1)

解法二：

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

pre=None

def isValidBST(self, root):

"""

:type root: TreeNode

:rtype: bool

"""

if root is None:

return True

Bool= self.isValidBST(root.left)

if self.pre!=None:

Bool=Bool and (self.pre.val

self.pre=root

Bool=Bool and self.isValidBST(root.right)

return Bool

二叉搜索树迭代器

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：

BSTIterator iterator = new BSTIterator(root); iterator.next(); // 返回 3 iterator.next(); // 返回 7 iterator.hasNext(); // 返回 true iterator.next(); // 返回 9 iterator.hasNext(); // 返回 true iterator.next(); // 返回 15 iterator.hasNext(); // 返回 true iterator.next(); // 返回 20 iterator.hasNext(); // 返回 false

提示： next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

解法 开始一直没想出来，一直想怎么找到输出节点后删除节点。其实可以用数组存储的。参考：https://blog.csdn.net/qq_17550379/article/details/86082379 有三种方法：

通过遍历(中序)将二叉树的数据存放到数组中，然后每次next操作时取出最小值即可。用heapq实现最小堆将左边不断压栈，那么栈中存放的就是从大到小的值。调用next的时候，我们只需要弹出栈顶元素即可，同时我们需要将right加入栈中(非递归先序遍历二叉树的思路)

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class BSTIterator(object):

def __init__(self, root):

"""

:type root: TreeNode

"""

self.root = root

self.stack = []

self.pushleft(self.root)

def pushleft(self, cur):

while cur:

self.stack.append(cur)

cur = cur.left

def next(self):

"""

@return the next smallest number

:rtype: int

"""

tmp = self.stack.pop()

self.pushleft(tmp.right)

return tmp.val

def hasNext(self):

"""

@return whether we have a next smallest number

:rtype: bool

"""

return True if self.stack else False

# Your BSTIterator object will be instantiated and called as such:

# obj = BSTIterator(root)

# param_1 = obj.next()

# param_2 = obj.hasNext()

Search in a Binary Search Tree

给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

例如，

给定二叉搜索树:

4

/ \

2   7

/ \

1   3

和值: 2 你应该返回如下子树:

2

/ \

1   3

在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

解法 比较简单

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

def searchBST(self, root, val):

"""

:type root: TreeNode

:type val: int

:rtype: TreeNode

"""

if not root:

return None

cur = root

while cur:

if val == cur.val:

return cur

elif val < cur.val:

cur = cur.left

else:

cur = cur.right

return None

Insert into a Binary Search Tree

给定二叉搜索树(BST)的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

例如,

给定二叉搜索树:

4

/ \

2   7

/ \

1   3

和 插入的值: 5

你可以返回这个二叉搜索树:

4

/   \

2     7

/ \   /

1   3 5

或者这个树也是有效的:

5

/   \

2     7

/ \

1   3

\

4

解法 正常的搜索，就按照叶子节点的方法插入

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

def insertIntoBST(self, root, val):

"""

:type root: TreeNode

:type val: int

:rtype: TreeNode

"""

if not root:

return TreeNode(val)

cur = root

while cur:

if val < cur.val:

if not cur.left:

cur.left = TreeNode(val)

return root

else:

cur = cur.left

else:

if not cur.right:

cur.right = TreeNode(val)

return root

else:

cur = cur.right

return root

Delete Node in a BST

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点； 如果找到了，删除它。 说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]

key = 3

5

/ \

3   6

/ \   \

2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

5

/ \

4   6

/     \

2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

5

/ \

2   6

\   \

4   7

解法 参考：https://blog.csdn.net/qq_39315740/article/details/89034263 删除节点主要有三种情况：

节点只存在左子树，那么我们直接用左子树代替根节点即可；节点只存在右子树，同样地，我们直接用右子树代替根节点；同时存在左右子树是比较复杂的情况，这是我们重点关注的情况。

这里我们优先采用右子树替换根节点的原则(当然左子树也可以)。 当我们找到需要删除的节点后，必须以右子树的最小节点(也就是右子树最左的节点)来代替被删除的节点

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

def deleteNode(self, root, key):

"""

:type root: TreeNode

:type key: int

:rtype: TreeNode

"""

if not root:

return None

if root.val < key:

root.right = self.deleteNode(root.right, key)

elif root.val > key:

root.left = self.deleteNode(root.left, key)

else:

if not root.left or not root.right:

root = root.left if root.left else root.right

else:

cur = root.right

while cur.left:

cur = cur.left

root.val = cur.val

root.right = self.deleteNode(root.right, cur.val)

return root

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

1

/

3

\

2

Output: [3,1,null,null,2]

3

/

1

\

2

Example 2:

Input: [3,1,4,null,null,2]

3

/ \

1   4

/

2

Output: [2,1,4,null,null,3]

2

/ \

1   4

/

3

Follow up:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

同样使用中序遍历即可，所以还是需要定义pre节点表示前驱节点。 有两个节点颠倒了，只需要找到两个节点的位置。用n1存储第一个错位的元素，n2存储第二个，然后交换就可以了。

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

def recoverTree(self, root):

"""

:type root: TreeNode

:rtype: None Do not return anything, modify root in-place instead.

"""

self.n1, self.n2, self.pre = None, None, None

self.inorder(root)

self.n1.val, self.n2.val = self.n2.val, self.n1.val

def inorder(self, root):

if root ==None:

return

self.inorder(root.left)

if self.pre!=None and self.pre.val > root.val:

if self.n1 == None:

self.n1=self.pre

self.n2=root

self.pre=root

self.inorder(root.right)

二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明： 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1

3

/ \

1   4

\

2

输出: 1 示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3

5

/ \

3   6

/ \

2   4

/

1

输出: 3 进阶： 如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

解法 二叉搜索树BST，左子树不大于父节点，右子树不小于父节点，要找到第k小的数字，也就是把树整理成从小到大的顺序，也就是中序遍历。

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

def kthSmallest(self, root, k):

"""

:type root: TreeNode

:type k: int

:rtype: int

"""

res = []

self.inorder(root, res, k)

return res[k-1]

def inorder(self, root, res, k):

if root:

self.inorder(root.left, res, k)

if len(res) >= k:

return res

res.append(root.val)

self.inorder(root.right, res, k)

Kth Largest Element in a Stream

设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

示例:

int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8 说明: 你可以假设 nums 的长度≥ k-1 且k ≥ 1。

解法 两种解法：

最小堆：比较简单，维护一个size为K的小顶堆，则堆顶元素即为第K大的元素。BST：给每个Node维护一个cnt，表示以它为根的树共多少节点。那么每个节点的所有右子树如果有m个节点，则该节点就是第m+1大的数。

最小堆：

from heapq import *

class KthLargest(object):

def __init__(self, k, nums):

"""

:type k: int

:type nums: List[int]

"""

self.heap = nums

self.k = k

heapify(self.heap)

while len(self.heap) > k:

heappop(self.heap)

def add(self, val):

"""

:type val: int

:rtype: int

"""

if len(self.heap) < self.k:

heappush(self.heap, val)

elif val > self.heap[0]:

heapreplace(self.heap, val)

return self.heap[0]

BST：

class Node(object):

def __init__(self, val):

self.val = val

self.cnt = 1

self.left = None

self.right = None

class KthLargest(object):

def __init__(self, k, nums):

"""

:type k: int

:type nums: List[int]

"""

self.root = None

self.k = k

for x in nums:

self.insert(x)

def add(self, val):

"""

:type val: int

:rtype: int

"""

self.insert(val)

return self.get_k(self.root, self.k)

def insert(self, x):

if not self.root:

self.root = Node(x)

return

cur = self.root

while cur:

cur.cnt += 1

if x < cur.val:

if not cur.left:

cur.left = Node(x)

return

else:

cur = cur.left

else:

if not cur.right:

cur.right = Node(x)

return

else:

cur = cur.right

def get_k(self, cur, k):

if not cur.right and k == 1:

return cur.val

if not cur.right:

return self.get_k(cur.left, k - 1)

if cur.right.cnt == k - 1:

return cur.val

if cur.right.cnt >= k:

return self.get_k(cur.right, k)

else:

return self.get_k(cur.left, k - cur.right.cnt - 1)

# Your KthLargest object will be instantiated and called as such:

# obj = KthLargest(k, nums)

# param_1 = obj.add(val)

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]  示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

def lowestCommonAncestor(self, root, p, q):

"""

:type root: TreeNode

:type p: TreeNode

:type q: TreeNode

:rtype: TreeNode

"""

if root.val == p.val or root.val == q.val:

return root

if (p.val < root.val and q.val > root.val) or (q.val < root.val and p.val > root.val):

return root

if p.val < root.val and q.val < root.val:

return self.lowestCommonAncestor(root.left, p, q)

else:

return self.lowestCommonAncestor(root.right, p, q)

class Solution(object):

def lowestCommonAncestor(self, root, p, q):

"""

:type root: TreeNode

:type p: TreeNode

:type q: TreeNode

:rtype: TreeNode

"""

pointer = root

while pointer:

if q.val < pointer.val and p.val < pointer.val:

pointer = pointer.left

elif q.val > pointer.val and p.val > pointer.val:

pointer = pointer.right

else:

return pointer

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

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

0

/ \

-3   9

/   /

-10  5

解法 数组nums是一个升序数组，所以根节点的位置一定是m = len(nums)//2 nums中索引值小于m的树都位于根节点的左子树上，而另一半位于根节点的右子树上，然后进行递归调用。

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

def sortedArrayToBST(self, nums):

"""

:type nums: List[int]

:rtype: TreeNode

"""

if not nums:

return None

mid = len(nums) // 2

root = TreeNode(nums[mid])

root.left = self.sortedArrayToBST(nums[:mid])

root.right = self.sortedArrayToBST(nums[mid + 1:])

return root

不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:  解法 动态规划：假设n个节点存在二叉排序树的个数是G(n)，因为根节点值不同，形成的二叉搜索树就不同，那么[1:n]范围内的n个数就有n个不同的选择 假设选取i作为根节点值，根据二叉搜索树的规则，[1:i−1]这i-1个数在其左子树上，[i+1:n]这n-i个数在其右子树上；对于左子树，又可以采用上述方法进行分解；对于右子树，同样可以采用上述方法进行分解。 让G(n)表示由连续的n个数形成的二叉搜索树的个数。所以当x为根节点时，其左子树节点个数为x - 1个，右子树节点为n - x，即f(i) = G(x - 1) * G(n - x),需要对G(0)和G(1)特殊处理，令其为1，即G(0)=G(1)=1

具体做法：让i表示连续i个数，dp[i]表示连续i个数能形成的BST的个数；j表示根节点的位置；最后返回dp[n]即可

class Solution:

def numTrees(self, n: 'int') -> 'int':

'''

'''

dp = [0] * (n+1)

dp[0],dp[1] = 1,1

#状态转移公式：dp(n) = dp(0)*dp(n-1)+dp(1)*dp(n-2)+...+dp(n-1)*dp(0)

for i in range(2,n+1):

for j in range(i):

dp[i] += dp[j] * dp[i-j-1]

return dp[n]

不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

输入: 3

输出:

[

[1,null,3,2],

[3,2,null,1],

[3,1,null,null,2],

[2,1,3],

[1,null,2,null,3]

]

解释:

以上的输出对应以下 5 种不同结构的二叉搜索树：

1         3     3      2      1

\       /     /      / \      \

3     2     1      1   3      2

/     /       \                 \

2     1         2                 3

解法 类似于上一题，从序列 1 …n 取出数字 i 并以它作为当前树的根节点。 那么就有 i - 1 个元素可以用来构造左子树，而另外的 n - i 个元素可以用于构造右子树。最后我们将会得到 G(i - 1) 棵不同的左子树，以及 G(n - i) 棵不同的右子树。 所以可以使用递归的方法，在序列 1 … i - 1 上重复前面的步骤来构造所有的左子树，之后对序列 i + 1 … n 也这样做以得到所有的右子树。 这么一来，我们就得到了根节点 i 和两个可能的左右子树列表。 最后一步是遍历两个列表，将左右子树和根节点链接起来。

注意：边界值的处理；属于排列组合的算法

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

def generateTrees(self, n):

"""

:type n: int

:rtype: List[TreeNode]

"""

def generate_trees(start, end):

if start > end:

return [None,]

all_trees = []

for i in range(start, end + 1):  # pick up a root

# all possible left subtrees if i is choosen to be a root

left_trees = generate_trees(start, i - 1)

# all possible right subtrees if i is choosen to be a root

right_trees = generate_trees(i + 1, end)

# connect left and right subtrees to the root i

for l in left_trees:

for r in right_trees:

current_tree = TreeNode(i)

current_tree.left = l

current_tree.right = r

all_trees.append(current_tree)

return all_trees

return generate_trees(1, n) if n else []

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

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

解法 后序遍历中，最后一个数字是根结点的值，数组的前面数字部分可分为两部分，一部分是左子树，一部分是右子树。我们根据二叉搜索树的性质可知，左子树的值要比根节点小，而右子树所有值要比根节点大。以此递归来判断所有子树。

# -*- coding:utf-8 -*-

class Solution:

def VerifySquenceOfBST(self, sequence):

# write code here

if not sequence:

return False

else:

return self.verify(sequence)

def verify(self, sequence):

if not sequence:

return True

# 根节点就是最后一个树，获取一下这个值，然后从数组中弹出去

root = sequence.pop()

# 找一下左右子树

index = self.findIndex(sequence, root)

# 细分到没有子结点作为终止条件

if not sequence[index:]:

return True

# 如果右边数组最小值都大于root，则说明没有问题。进一步细分

elif min(sequence[index:]) > root:

left = sequence[:index]

right = sequence[index:]

return self.verify(left) and self.verify(right)

return False

# 定义一个函数，来找到左右子树的分界线

# 左子树的值比根节点小，右子树的值比根节点大，以此为左右子树的界限

def findIndex(self, sequence, root):

for i, seq in enumerate(sequence):

if sequence[i]>root:

return i

return len(sequence)

二叉搜索树与双向链表

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

解法 参考：https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5?answerType=1&f=discussion

辅助数组：最容易想到的，是用一个数组来存储中序遍历的节点，然后再从头到尾，建立节点前后的连接关系。线索化二叉树：因为二叉排序树中序遍历的结果是排好序的，很容易联想到用线索化二叉树的方法去做，用一个全局变量去保存前一个节点，然后再去创建节点之间的关系。只要pre不空，就创建关系，创建后就是链表了。但是要注意，返回的双向链表是降序排列的，那我们有两种解决方法，第一种是再遍历一遍得到的结果，将节点的最后一个结果返回。第二种是设置一个变量来记录。优化：我们受到惯性思维的约束，每次都是想着中序遍历先遍历左子树，再遍历根节点，再遍历右子树。那既然第二种方法得到的二叉树是降序的，那我先遍历右子树，再遍历根节点，再遍历左子树不就可以了么

方法二：

class Solution:

def __init__(self):

self.pre = None

self.root = None

def Convert(self, pRootOfTree):

# write code here

if not pRootOfTree:

return None

self.Convert(pRootOfTree.left)

if self.root == None:

self.root = pRootOfTree

if self.pre:

pRootOfTree.left = self.pre

self.pre.right = pRootOfTree

self.pre = pRootOfTree

self.Convert(pRootOfTree.right)

return self.pre

方法三：

# -*- coding:utf-8 -*-

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

def __init__(self):

self.pre = None

def Convert(self, pRootOfTree):

# write code here

if pRootOfTree == None:

return None

self.Convert(pRootOfTree.right)

if self.pre != None:

pRootOfTree.right = self.pre

self.pre.left = pRootOfTree

self.pre = pRootOfTree

self.Convert(pRootOfTree.left)

return self.pre

二叉搜索树转换成循环双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。  我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。  特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

解法 同上，两类方法

进行中序遍历的时候，将所有 node 存放在一个数组中，依次遍历数组，改造 right 指针指向下一个元素，left 指针指向前一个元素，单独处理首尾的连接为了能够完成双向的指向，我们必须同时有两个 node。让第一个 node 的 right 指向第二个 node，同时让第二个 node 的 left 指向第一个node。第一个 node 使用一个全局遍历 self.pre，第二个 node 使用当前点 root。

方法一：

class Solution:

def __init__(self):

self.list = []

def inOrderTraverse(self, root):

if not root:

return None

self.inOrderTraverse(root.left)

self.list.append(root)

self.inOrderTraverse(root.right)

def treeToDoublyList(self, root: 'Node') -> 'Node':

if not root:

return None

self.inOrderTraverse(root)

l = len(self.list)

for i in range(l-1):

self.list[i].right = self.list[i+1]

self.list[l-1-i].left = self.list[l-2-i]

self.list[l-1].right = self.list[0]

self.list[0].left = self.list[l-1]

return self.list[0]

方法二：

class Solution:

def __init__(self):

self.pre = None

self.head = None

def inOrderTraverse(self, root):

if not root:

return None

# left DFS

self.inOrderTraverse(root.left)

if self.pre == None:

self.pre = root

self.head = root # This is the left most node -> head

else:

self.pre.right = root   # Pre.right -> current node

root.left = self.pre    # current node.left -> pre

self.pre = root         # change pre to current node

# right DFS

self.inOrderTraverse(root.right)

def treeToDoublyList(self, root: 'Node') -> 'Node':

if not root:

return None

# Inorder traverse

self.inOrderTraverse(root)

# Link head and tail

self.head.left = self.pre

self.pre.right = self.head

return self.head

二叉搜索树序列

从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉搜索树，输出所有可能生成此树的数组。

示例： 给定如下二叉树

2

/ \

1   3

返回：

[ [2,1,3], [2,3,1] ]

解法  会出现这样的一个结果 [[3,0,1,2,4],[3,0,1,4,2],[3,0,4,1,2],[3,4,0,1,2]] 我们发现其实并不是每个节点的后面都是他的一个子节点，0后面也可能出现4，1后面也可能出现4，…，说明左右节点也可以交替出现！

具体做法：

3这个节点的左右节点[0, 4]，那么下一个节点就要在[0, 4]中选择如果下个节点是0，其左右节点[1], 那么0后面的节点可能有哪些呢？–> [4]+[1]如果下个节点是4，没有子节点[ ], 那么1后面的节点可能有哪些呢？–> [0]+[]

所以还是dfs递归全排列的方法：除了res和tmp外，还需要多加一个queue的队列，用来存储左右子节点。

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

def BSTSequences(self, root):

"""

:type root: TreeNode

:rtype: List[List[int]]

"""

if not root:

return [[]]

res, queue = [], []

tmp = [root.val]

self.dfs(root, queue, tmp, res)

return res

def dfs(self, root, queue, tmp, res):

if root.left:

queue.append(root.left)

if root.right:

queue.append(root.right)

if not queue:

res.append(tmp)

return

for i, node in enumerate(queue):

self.dfs(node, queue[:i] + queue[i + 1:], tmp + [node.val], res)