宁波手机网站建设,做网站的项目开发计划书,标书制作软件免费版,wordpress写文章分段leetcode刷题 | 关于二叉树的题型总结3 文章目录leetcode刷题 | 关于二叉树的题型总结3题目连接递增顺序搜索树二叉搜索树中的中序后继把二叉搜索树转换为累加树二叉搜索树迭代器题目连接
897. 递增顺序搜索树 - 力扣#xff08;LeetCode#xff09;
剑指 Offer II 053. 二…leetcode刷题 | 关于二叉树的题型总结3 文章目录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);}
}使用二分查找到找到curp的节点使用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;}
}使用右中左逆序中序遍历的方式并使用栈来存放前一个节点
当curnull时遍历到了叶子节点dep.poll() 得到该节点的父节点将cur 该父节点
更新cur父节点的val值题目要求值等于原树中大于或等于 node.val 的值之和使用sum来保存和
因为使用右中左的遍历顺序sum始终都是累加
class Solution {public TreeNode convertBST(TreeNode root) {int sum 0;DequeTreeNode 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 {ListTreeNode 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 {DequeTreeNode 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();}
}
