网站建站好处,中国建筑信息查询平台,黄页网站建设黄页网站建设,开源企业建站系统php题目
给定一棵二叉搜索树#xff0c;请将它的每个节点的值替换成树中大于或等于该节点值的所有节点值之和。假设二叉搜索树中节点的值唯一。例如#xff0c;输入如图8.10#xff08;a#xff09;所示的二叉搜索树#xff0c;由于有两个节点的值大于或等于6#xff08;即…题目
给定一棵二叉搜索树请将它的每个节点的值替换成树中大于或等于该节点值的所有节点值之和。假设二叉搜索树中节点的值唯一。例如输入如图8.10a所示的二叉搜索树由于有两个节点的值大于或等于6即节点6和节点7因此值为6节点的值替换成13其他节点的值的替换过程与此类似所有节点的值替换之后的结果如图8.10b所示。
分析
如果能够按照节点值从大到小按顺序遍历二叉搜索树那么只需要遍历一次就够了因为遍历到一个节点之前值大于该节点的值的所有节点已经遍历过。通常的中序遍历是先遍历左子树再遍历根节点最后遍历右子树由于左子树节点的值较小右子树节点的值较大因此总体上就是按照节点的值从小到大遍历的。如果要按照节点的值从大到小遍历那么只需要改变中序遍历的顺序先遍历右子树再遍历根节点最后遍历左子树这样遍历的顺序就颠倒过来了。
解
public class Test {public static void main(String[] args) {TreeNode node1 new TreeNode(1);TreeNode node2 new TreeNode(2);TreeNode node3 new TreeNode(3);TreeNode node4 new TreeNode(4);TreeNode node5 new TreeNode(5);TreeNode node6 new TreeNode(6);TreeNode node7 new TreeNode(7);node4.left node2;node4.right node6;node2.left node1;node2.right node3;node6.left node5;node6.right node7;TreeNode result convertBST(node4);System.out.println(result);}public static TreeNode convertBST(TreeNode root) {StackTreeNode stack new Stack();TreeNode cur root;int sum 0;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {stack.push(cur);cur cur.right;}cur stack.pop();sum cur.val;cur.val sum;cur cur.left;}return root;}
}
