230.BST中第k小的元素
基本思想:
BST的中序遍历是升序序列。下标为k-1的元素就是第k个元素。
具体实现:
中序遍历后,找下标为k-1的元素。
代码:
class Solution: def kthSmallest(self, root, k): """ :type root: TreeNode :type k: int :rtype: int """ def inorder(r): return inorder(r.left) + [r.val] + inorder(r.right) if r else [] return inorder(root)[k - 1]
538.把BST转换为累加树
基本思想:
每个节点的值修改为原来的节点值加上所有大于它的节点值之和。反序中序遍历,
具体实现:
定义一个全局变量sum用来记录当前遍历节点cur与之前节点的和,这样方便累加
类似于530题、501题
1、递归参数以及返回值
返回值:无,因为要遍历整棵树
参数:根节点
2、递归终止条件
遇到空节点就终止
3、确定单层递归的逻辑
用右中左来遍历二叉树,
中节点的处理逻辑就是让cur的数值加上前一个节点的数值
代码:
class Solution { int sum; public TreeNode convertBST(TreeNode root) { sum = 0; convertBST1(root); return root; } public void convertBST1(TreeNode root){ if (root == null) return; convertBST1(root.right); sum += root.val; root.val = sum; convertBST1(root.left); } }
迭代法:
class Solution { public TreeNode convertBST(TreeNode root) { int sum = 0; Stack<TreeNode> st = new Stack<>(); TreeNode cur = root; while(cur != null || !st.empty()){ if (cur != null){ st.push(cur); cur = cur.right; } else { cur = st.pop(); sum += cur.val; cur.val = sum; cur = cur.left; } } return root; } }
99、恢复一颗BST
基本思想:
中序遍历是按顺序的,遍历结果放到一个列表
列表发现顺序不对,交换就行
具体实现:
1、中序遍历二叉树后。将遍历结果保存到list
2、扫描遍历的结果,找出错误节点并保存
x保存的是错误的第一个数,循环中只保存一次
y保存的是错误的第二个数,遍历到最后才能确定y
这段代码,有水平,背会吧
3、交换错误的节点值
代码:
class Solution(object): def recoverTree(self, root): nodes = [] # 中序遍历二叉树,并将遍历的结果保存到list中 def dfs(root): if not root: return dfs(root.left) nodes.append(root) dfs(root.right) dfs(root) x = None y = None pre = nodes[0] # 扫描遍历的结果,找出可能存在错误交换的节点x和y for i in xrange(1,len(nodes)): if pre.val>nodes[i].val: y=nodes[i] if not x: x = pre pre = nodes[i] # 如果x和y不为空,则交换这两个节点值,恢复二叉搜索树 if x and y: x.val,y.val = y.val,x.val