编程里（通过自己具体的观察从第一次到第二次、第三次观察之间的关系）
* 编程里有很重要的一个思维：就是记录“第一次的结果”，然后等到走到“第二次的结果”时进行一些操作
* 可能是把第二次的结果与第一次进行比较，然后进行一些操作，
* 也可能是（比较之后）将第二次结果覆盖掉第一次结果
* 所以编程里非常重要的变量：标记变量：即记录“第一次的结果”（前一次的结果），留个“第二次的结果”（当前的结果）进行比较
1、 98_验证二叉搜索树：【 https://leetcode-cn.com/problems/validate-binary-search-tree/】
//中序遍历（迭代法）~ 从小到大啦（用一个变量记录前一次“第一次”，当前本次（第二次）与之对比） //这里的记录变量是：inorder class Solution { public boolean isValidBST(TreeNode root) { Deque<TreeNode> stack = new LinkedList<TreeNode>(); double inorder = -Double.MAX_VALUE; TreeNode node = root; while (!stack.isEmpty() || node != null) { while (node != null) { stack.push(node); node = node.left; } // 即根 node = stack.pop(); // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树 if (node.val <= inorder) { return false; } inorder = node.val; // 判断该点 node = node.right; } return true; } }
2、 145_二叉树的后序遍历：【https://leetcode-cn.com/problems/binary-tree-postorder-traversal/submissions/】
//迭代： /** 后序：【左右根】：左左左，左到不能再左了，跳出（当前结点可能是最左边的结点（是一个根（它的左是null，是它跳出的条件））），【开始找右边】： （1）没有右边/本次的右结点是上一次的结点，则本次是一个根（因为 左 右 根）：添加根 prev = root; //第一次的结点，可能是下一次（根）的右结点，需要标记留个下次比较 root = null;（不加超出内存，这是why？？？） （2）有右边（把根push回去），从右子树开始啦：（左右根） */ List<Integer> list = new ArrayList<>(); public List<Integer> postorderTraversal(TreeNode root) { if(root == null) return list; Deque<TreeNode> stack = new LinkedList<>(); TreeNode prev = null; while(!stack.isEmpty() || root != null) { while(root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (root.right == null || root.right == prev) { list.add(root.val); prev = root; root = null; //不加：超出内存 } else { stack.push(root); root = root.right; } } return list; }
3、 114_二叉树展开为链表：【 https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/】
//题意：左指针变成null，右指针指向下个结点 //记录第一个结点prevNode： //然后 走到第二个结点currNode，让第一个结点prev 的左指针指向null，右指针 指针 第二个结点 public void flatten2(TreeNode root) { if (root == null) { return; } Deque<TreeNode> queue = new LinkedList<TreeNode>(); queue.push(root); TreeNode prev = null; while (!queue.isEmpty()) { TreeNode curr = queue.pop(); if (prev != null) { //通过 prev != null 判断得知：当前结点是第二个（来到了下一次）啦 prev.left = null; prev.right = curr; } TreeNode left = curr.left, right = curr.right; if (right != null) { queue.push(right); } if (left != null) { queue.push(left); } prev = curr; //记录第一次“前一次的结果” } }
