LeetCode 897. Increasing Order Search Tree
原创LeetCode 897. Increasing Order Search Tree
原创
897. Increasing Order Search Tree
Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the
root of the tree, and every node has no left child and only 1 right child.
Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]
5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9题目大意：将一个BST，转化为一个只有右孩子的树，并且，这个树从根节点到叶子节点是从小到大排列的。
错误解法：
TreeNode prev1 ;
TreeNode dunny = prev1;
public TreeNode increasingBST(TreeNode root) {
increasingBST_helper(root);
return dunny;
}
public void increasingBST_helper(TreeNode root) {
if (root == null) return;
increasingBST_helper(root.left);
if (prev1!=null) {
prev1.right = root;
root.left = null;
}
prev1 = root;
increasingBST_helper(root.right);
}
这个解法思路没有什么错误，但是最终的结果总是返回null?是什么原因呢？
解法一：
个人觉得解法一较为容易理解，既然最后的树从根节点到叶子节点是从小到大排列的，我们知道，BST采用中序遍历就是从小到大依次遍历树。于是我们采用prev1节点来记录上一个遍历的节点，用dunny来记录最终树的根节点，于是可以很容易的写出一下程序，个人觉得算法的效率一般，至少不会很差吧，属于一个中规中矩的树的递归。
TreeNode prev1 ;
TreeNode dunny = prev1;
public TreeNode increasingBST(TreeNode root) {
increasingBST_helper(root);
return dunny;
}
public void increasingBST_helper(TreeNode root) {
if (root == null) return;
increasingBST_helper(root.left);
if (prev1!=null) {
prev1.right = root;
root.left = null;
}else {
dunny = root;
}
prev1 = root;
increasingBST_helper(root.right);
}需要注意的是，什么时候给dunny赋值呢？这种错误是我经常犯的错误，如果再定义dunny的时候让dunny指向一个没有初始化的prev1，后面不再对dunny做其他赋值操作的话，这样的返回结果是为null的，因为dunny指向prev1的时候，prevd1还没有初始化，所以，这个时候prev1并没有指向一个地址，prev1仍然指向null，即使后面对prev1进行了赋值操作，但是这个时候并不会影响到dunny，因此，这就是为什么之前一直返回为null的原因。
解法二：
解法二的思路与解法一，并没有原理上本质的区别，对错误的解法进行了思考后，可以采用虚拟投节点的方式更好的处理标记头结点的问题，我们采用dunny做为虚拟头结点，这节点不包含于最终的结果，这样就省去了一个解法一中的判断条件，不需要考虑何时给最终结果的投节点做标记的情况。实际上，虚拟头结点（英文：dunny）在链表中的使用更加广泛，这样的好处是很好的处理头结点的问题。
TreeNode prev1 = new TreeNode(0);
TreeNode dunny = prev1;
public TreeNode increasingBST(TreeNode root) {
increasingBST_helper(root);
return dunny.right;
}
public void increasingBST_helper(TreeNode root) {
if (root == null) return;
increasingBST_helper(root.left);
prev1.right = root;
root.left = null;
prev1 = root;
increasingBST_helper(root.right);
}如果你觉得采用global variable 不爽，那也可以很容易改为函数变量。
解法三：
解法三的思路是我在讨论区看到的别人的解法，这个递归的思路，个人感觉并没有之前的好理解，但是代码量比上面的要少。
public TreeNode increasingBST(TreeNode root) {
return helper(root, null);
}
public TreeNode helper(TreeNode root, TreeNode tail) {
if (root == null) return tail;
TreeNode res = helper(root.left, root);
root.left = null;
root.right = helper(root.right, tail);
return res;
}下面添加两行输出，把每次的递归参数打印出来，也许会更好理解。
public TreeNode increasingBST(TreeNode root) {
return helper(root, null);
}
public TreeNode helper(TreeNode root, TreeNode tail) {
///////////////////////////////////////////////////////////////////////////////
if (root!=null)System.out.print(root.val); else System.out.print("null");
System.out.print(" ");
if (tail!=null)System.out.println(tail.val); else System.out.println("null");
///////////////////////////////////////////////////////////////////////////////
if (root == null) return tail;
TreeNode res = helper(root.left, root);
root.left = null;
root.right = helper(root.right, tail);
return res;
} 5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9输出为：
root tail:
5 null
3 5
2 3
1 2
null 1
null 2
null 3
4 5
null 4
null 5
6 null
null 6
8 null
7 8
null 7
null 8
9 null
null 9
null null总结，关于BST的问题，考察中序遍历的问题较为常见，也会存在各种变形，需要你仔细思考，将问题转化为我们熟知的那些树的特性上去求解。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。