做网站要用到哪些技术,承德市人才信息网,wordpress判断自定义页面,舆情信息理解题意#xff1a; 所谓累加树#xff1a;对于每个节点#xff0c;将所有比它大的点累加于这一点。 而二叉搜索树#xff1a;任何一个中间节点#xff0c;都大于左子树任何节点#xff0c;小于右子树所有节点。 而二叉搜索树中序排列是严格单调递增的序列。 所以二叉搜… 理解题意 所谓累加树对于每个节点将所有比它大的点累加于这一点。 而二叉搜索树任何一个中间节点都大于左子树任何节点小于右子树所有节点。 而二叉搜索树中序排列是严格单调递增的序列。 所以二叉搜索树累加树的话则是将右子树的节点加到中间节点再将中间节点加到左子树。 从中序序列来看可以使用双指针节点一个pre指针一个cur指针。从后往前遍历将pre指向比cur大的值始终将pre加到cur。 从树的结构来看pre之上前一位比cur值大的节点cur指向当前最大的节点。 树的遍历顺序为右中左。 解题方法 递归 迭代 1.递归
节点处理顺序为右中左pre总是指向比当前值大的值的累加和。
public TreeNode convertBST(TreeNode root) {AddBST(root);return root;}//指向比当前值大的值的累加int pre0;public void AddBST(TreeNode cur) {if(curnull)return;if(cur.right!null){AddBST(cur.right);}cur.valpre;precur.val;if(cur.left!null) AddBST(cur.left);}
2.迭代
入栈顺序总是左中右出栈顺序右中左pre总是指向比当前值大的值的累加和。 public TreeNode convertBST(TreeNode root) {if(rootnull) return root;int pre0;StackTreeNode stacknew Stack();stack.push(root);while(!stack.isEmpty()){TreeNode curstack.pop();if(cur!null){if(cur.left!null) stack.push(cur.left);stack.push(cur);stack.push(null);if(cur.right!null) stack.push(cur.right);}else{curstack.pop();cur.valpre;precur.val;}}return root;}
3.分析 时间复杂度 递归O(n) 迭代O(n) 空间复杂度 递归O(n) 迭代O(2n)
