二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下,恢复这棵树。
示例 1:
输入: [1,3,null,null,2]
1
/
3
\
2
输出: [3,1,null,null,2]
3
/
1
\
2
示例 2:
输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
进阶:
- 使用 O(n) 空间复杂度的解法很容易实现。
- 你能想出一个只使用常数空间的解决方案吗?
解题思路:
非递归中序遍历(用栈深度优先搜索)这棵树,正常为递增序列,找到交换的两个节点
Java代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void recoverTree(TreeNode root) {
TreeNode pre = new TreeNode(Integer.MIN_VALUE), p = null, q = null;
Stack<TreeNode> stack = new Stack<>();
while(null != root){
stack.push(root);
root = root.left;
}
while(!stack.isEmpty()){
TreeNode treeNode = stack.pop();
if(treeNode.val < pre.val){
if(null == p){
p = pre;
q = treeNode;
}
else{
q = treeNode;
}
}
pre = treeNode;
if(null != treeNode.right){
stack.push(treeNode.right);
while(null != stack.peek().left)
stack.push(stack.peek().left);
}
}
int tmp = p.val;
p.val = q.val;
q.val = tmp;
}
}
版权声明:本文为weixin_38823568原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。