找到搜索二叉樹中兩個錯誤的節點
解題思路
中序遍歷二叉搜索樹，用指標pre記錄上一個訪問的節點 ，找到兩個逆序處cur.val < pre.val即可，注意的是第一次first=[prev, cur]中的pre, 第二次second=[prev, cur]中的cur， 因為題意最終要求回傳的結果升序排列，所以回傳new int{second.val, first.val}
實作代碼
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode類 the root
* @return int整型一維陣列
*/
public int[] findError (TreeNode root) {
// write code here
if(root == null || (root.left == null && root.right == null)){
return new int[]{-1, -1};
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode pre = null;
TreeNode first = null;
TreeNode second = null;
while(!stack.isEmpty() || cur != null){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if(pre != null && cur.val < pre.val){
if(first == null){
first = pre;
}
else{
second = cur;
break;
}
}
pre = cur;
cur = cur.right;
}
return new int[]{second.val, first.val};
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/241930.html
標籤：其他