饭后小甜点leetcode——恢复二叉树

有一种题，需要在遍历二叉树的时候，keep一个last指针，始终指向上一个遍历到的节点。

恢复二叉树

恢复二叉搜索树

【思路】二叉搜索树在中序遍历的时候，得到的list应该如图中粉色点点那样递增，但如果其中有两个节点被放错地方了，则这两个节点则会像绿色点点一样，

所以在第一次发现last节点比current节点大的时候，如果first节点还没有赋值过，则说明是图中第一个圈中的情况，然后把last节点赋值给first，到了再一次发现last比current大的时候，而且first已经有值了，就是圈2中的情况，则此时second节点更新为current节点。

public class Solution {public TreeNode last;public TreeNode first;public TreeNode second;public void RecoverTree(TreeNode root){DFS(root);var temp = first.val;first.val = second.val;second.val = temp;}public void DFS(TreeNode root){if(root==null){return;}DFS(root.left);if(last!=null&&last.val>root.val){if(first==null){first = last;}second = root;}last = root;DFS(root.right);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！