leetcode刷题 | 关于二叉树的题型总结3

题目连接

897. 递增顺序搜索树 - 力扣（LeetCode）

剑指 Offer II 053. 二叉搜索树中的中序后继 - 力扣（LeetCode）

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

173. 二叉搜索树迭代器 - 力扣（LeetCode）

递增顺序搜索树

二叉树本身是有序的，可以采用左中右的遍历顺序，使用一个prev节点保存前一个结点

class Solution {TreeNode prev = new TreeNode(-1);TreeNode node = prev;public TreeNode increasingBST(TreeNode root) {dfs(root);return node.right;}public void dfs(TreeNode root){if(root == null) return ;dfs(root.left);prev.right = root;root.left = null;prev = root;dfs(root.right);}
}

二叉搜索树中的中序后继

dfs+中序遍历

class Solution {TreeNode res = null;public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {dfs(root,p);return res;}public TreeNode dfs(TreeNode root,TreeNode p){if(root == null) return null;if(root.val > p.val){res = root;return inorderSuccessor(root.left,p);}else return inorderSuccessor(root.right,p);}
}

使用二分查找到找到cur=p的节点，使用prev记录cur的root节点

然后判断cur节点是否有右子树，如果存在则返会右子树的最左边的节点

如果没有右子树那么直接返会prev，因为pre > cur = p

class Solution {   public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {TreeNode cur = root;TreeNode prev = null;while(cur != p){if(cur.val > p.val){prev = cur;cur = cur.left;}else{cur = cur.right;}}  if(cur.right != null){cur = cur.right;while(cur.left != null){cur = cur.left;}return cur;}return prev;}
}

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

class Solution {int sum = 0;public TreeNode convertBST(TreeNode root) {if(root == null) return null;convertBST(root.right);root.val += sum; //将当前节点值和大于当前节点值的和相加sum = root.val; convertBST(root.left);return root;}  
}

使用右中左逆序中序遍历的方式并使用栈来存放前一个节点

当cur=null时遍历到了叶子节点，dep.poll() 得到该节点的父节点，将cur = 该父节点

更新cur父节点的val值，题目要求值等于原树中大于或等于 node.val 的值之和，使用sum来保存和

因为使用右中左的遍历顺序，sum始终都是累加

class Solution {public TreeNode convertBST(TreeNode root) {int sum = 0;Deque<TreeNode> deq = new ArrayDeque();      TreeNode cur = root;while(!deq.isEmpty() || cur != null){if(cur != null){deq.push(cur);cur = cur.right;}else{cur = deq.poll();sum += cur.val;cur.val = sum;cur = cur.left;}}return root;}
}

二叉搜索树迭代器

先获得中序遍历结果，然后遍历

class BSTIterator {List<TreeNode> list = null;int index;int siez;public BSTIterator(TreeNode root) {list = new ArrayList<>();index = -1;dfs(root);this.siez = list.size();}public int next() {return list.get(++index).val;}public boolean hasNext() {if (index >= siez-1) return false;return true;}public void dfs(TreeNode root){if (root == null) return ;dfs(root.left);list.add(root);dfs(root.right);}
}

使用栈存入全部的左子节点和根节点

class BSTIterator {Deque<TreeNode> deq = new ArrayDeque<>();public BSTIterator(TreeNode root) {TreeNode node  = root;while (node != null){deq.push(node);node = node.left;}}public int next() {TreeNode cur = deq.poll();if(cur.right != null){TreeNode node = cur.right;while(node != null){deq.push(node);node = node.left;//把所有的左节点都放入deq}}return cur.val;}public boolean hasNext() {return !deq.isEmpty();}
}