未命名分组 - 二叉树-trie-并查集 - 《数据结构 · Leetcode · SQL · 刷题笔记》

二叉树

222. 完全二叉树的节点个数

思路1：可以使用DFS的模板或者直接一个递归得到答案

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        return countNodes(root.left)+countNodes(root.right)+1;
    }
}

但是这样没有用到题目中完全二叉树的特性
思路2：完全二叉树的特性，最后一层依次铺满。我们可以首先计算获得左右子树的高度（left）如果高度一致，说明在这一层满或者右子树还没满，但是可以把左子树的个数计算了。 left！=right的话，说明left侧有空的节点。但是右子树是满的。所以可以提前先计算右子树的个数。

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = countLevel(root.left);
        int right = countLevel(root.right);
        if(left == right){
            return countNodes(root.right)+(1<<left);
        }else {
            return countNodes(root.left)+(1<<right);
        }
    }

    private int countLevel(TreeNode root) {
        int level = 0;
        while (root!=null){
            level++;
            root = root.left;
        }
        return level;
    }
}

103. 二叉树的锯齿形层次遍历

思路一：队列（BFS）
因为是锯齿状的获取里面的数值。我的想法就是改变队列的入队方式，使用一个flag变量来代表奇偶，true的时候先插入左节点，后插入右节点。插入的方式都是插入到前面。

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        // 标志位 true 代表先左后右 false 代表先右后左
        if(root == null){
            return res;
        }
        boolean flag = true;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> tmp;
        LinkedList<TreeNode> tmpQueue;
        while (!queue.isEmpty()){
            int size = queue.size();
            tmp = new ArrayList<>();
            tmpQueue = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(flag){
                    if(node.left!=null){
                        tmpQueue.addFirst(node.left);
                    }
                    if(node.right!=null){
                        tmpQueue.addFirst(node.right);
                    }
                }else {
                    if(node.right!=null){
                        tmpQueue.addFirst(node.right);
                    }
                    if(node.left!=null){
                        tmpQueue.addFirst(node.left);
                    }
                }
            }
            flag= !flag;
            queue = tmpQueue;
            res.add(new LinkedList<>(tmp));
        }
        return res;
    }
}

思路二：

上面的想法是插入队列的方式不同，其实我们可以改变一下思路，节点加入队列的方式不变，可以改变加入每一层的结果方式不同。简单来说就是使用一个奇偶变量来判断这一层是从头开始插入的还是从尾巴开始插入的。

        List<List<Integer>> res = new LinkedList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        if(root == null){
            return res;
        }

        queue.add(root);
        boolean flag = true;
        LinkedList<Integer> tmp;
        while (!queue.isEmpty()){
            int size = queue.size();
            tmp = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (flag){
                    tmp.add(node.val);
                }else {
                    tmp.addFirst(node.val);
                }
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!= null){
                    queue.add(node.right);
                }
            }
            res.add(new LinkedList<>(tmp));
            flag = !flag;
        }
        return res;

129. 求根到叶子节点数字之和

dfs的方法，记录一下cur的数值，如果到了最底层的话就把这个结果加上去。

class Solution {
    int res = 0;
    public int sumNumbers(TreeNode root) {
        dfs(root,0);
        return res;
    }
    private void dfs(TreeNode root,int cur){
        if(root == null){
            return;
        }
        cur*=10;
        cur+=root.val;
        if(root.left==null && root.right==null){
            res+=cur;
        }
        dfs(root.left,cur);

        dfs(root.right,cur);

    }
}

530. 二叉搜索树的最小绝对差

二叉搜索树的定义中，比root 大的节点在其右边，比他小的节点在其左边。中序遍历可以获取到一个从小到大排列的顺序。中序遍历的搜索顺序如下：左节点，根节点，右节点。我们可以使用一个全局的变量来记录一下前一个节点的值。每一次都可以跟当前的节点进行计算，然后计算其差值。获得到最小值。

class Solution {
    int pre = -1;
    int res = Integer.MAX_VALUE;
    /*思路 作为一个二叉搜索树，中序遍历的话可以得到数列的排序好的顺序。*/
    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return res;
    }

    private void inorder(TreeNode root) {
        if(root == null){
            return;
        }
        inorder(root.left);
        if(pre<0){
            pre = root.val;
        }else {
            res = Math.min(res,root.val-pre);
            pre = root.val;
        }
        inorder(root.right);
    }
}

145. 二叉树的后序遍历

接下来我们思考一下前序遍历和后序遍历之间的关系：

前序遍历顺序为：根 -> 左 -> 右

后序遍历顺序为：左 -> 右 -> 根

如果1：我们将前序遍历中节点插入结果链表尾部的逻辑，修改为将节点插入结果链表的头部

那么结果链表就变为了：右 -> 左 -> 根

如果2：我们将遍历的顺序由从左到右修改为从右到左，配合如果1

那么结果链表就变为了：左 -> 右 -> 根

这刚好是后序遍历的顺序

基于这两个思路，我们想一下如何处理：

修改前序遍历代码中，节点写入结果链表的代码，将插入队尾修改为插入队首

修改前序遍历代码中，每次先查看左节点再查看右节点的逻辑，变为先查看右节点再查看左节点

public class Solution145 {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        LinkedList<Integer> res =  new LinkedList<>();

        while (root!= null|| !stack.isEmpty()){
            if(root!=null){
                stack.push(root);
                res.addFirst(root.val);
                root = root.right;
            }else {
                root = stack.pop().left;
            }
        }
        return res;
    }
}

117. 填充每个节点的下一个右侧节点指针 II

这是一道层序遍历的题目，每一次把这一层的节点指向下一个节点。需要注意的点就在于next的指针不要指向下一层的节点。

class Solution {
    public Node connect(Node root) {
                ArrayDeque<Node> queue = new ArrayDeque<>();
        if(root== null){
            return null;
        }
        queue.addLast(root);

        while (!queue.isEmpty()){
            int size =  queue.size();
            // System.out.println("size: "+size);
            for (int i = 0; i < size; i++) {

                Node pre = queue.pollFirst();
                // System.out.println("pre.val:  "+pre.val);
                if(i == size-1){
                    pre.next = null;
                }else {
                    pre.next = queue.peek();
                }
                if(pre.left!=null){
                    queue.addLast(pre.left);
                }
                if(pre.right!=null){
                    queue.addLast(pre.right);
                }
            }
        }
        return root;
    }
}

106. 从中序与后序遍历序列构造二叉树

和从前序后序恢复一个二叉树有一点类似，就是将两个数组进行一个切分，看一下

617. 合并二叉树

思路:
对于这种题目，合并的情况。最好的方法是每一层都重新来简历这个节点。生成当前的节点，递归下面的层生成新的数据。
蛮有趣的.

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1 == null && t2 == null){
            return null;
        }

        TreeNode root = new TreeNode((t1==null?0:t1.val)+(t2==null?0:t2.val));

        root.left = mergeTrees((t1==null?null:t1.left),(t2==null?null:t2.left));
        root.right = mergeTrees((t1==null?null:t1.right),(t2==null?null:t2.right));
        return root;
    }
}

538. 把二叉搜索树转换为累加树

第一个想到的中序遍历，中序遍历可以获得二叉搜索树的从小到大的排序。而这道题的意思其实是让我们从后开始往前遍历。使用一个num来记录累加值。

class Solution {
    int num = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root != null){
            convertBST(root.right);
            root.val+= num;
            num =root.val;
            convertBST(root.left);
            return root;
        }
        return null;
    }
}

257. 二叉树的所有路径

思路：
对于当前的节点，如果是根节点的话，加入到结果里面去。对于不是当前的节点，加-> 并且DFS到下一层去。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<String> res = new LinkedList<>();
    public List<String> binaryTreePaths(TreeNode root) {

        if(root == null){
            return res;
        }

        dfs(root,"");
        return res;
    }
    private void dfs(TreeNode root, String s) {
        StringBuilder sb = new StringBuilder(s);
        if(root != null){
            sb.append(root.val);

            if(root.left == null && root.right == null){
                res.add(sb.toString());
            }else {
                sb.append("->");
                dfs(root.left,sb.toString());
                dfs(root.right,sb.toString());
            }
        }
    }
}

109. 有序链表转换二叉搜索树

使用快慢的指针，到达中点之后把这个节点设置为root，递归函数的返回值就是一段链表的中点。

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null){
            return null;
        }
        else if(head.next == null){
            return new TreeNode (head.val);
        }
        ListNode pre = head;
        ListNode p = pre.next;
        ListNode q = p.next;

        while (q!=null && q.next!=null){
            pre = pre.next;
            p = p.next;
            q = q.next.next;
        }

        pre.next = null;
        TreeNode root = new TreeNode(p.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(p.next);
        return root;
    }
}

110. 平衡二叉树

刚刚开始的构思是我算出左子树和右子树的深度，如果这个深度是小于2 的，那就说明这个树是一个平衡的。
单着这样是错误的，因为我只计算了root下的左子树和右子树情况。这道题可以看出

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

所以其实对于第一版的代码，我需要做的是，加入对于每一个子树的判断。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return Math.abs(depth(root.left)-depth(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {

        if(root == null)return 0;

        return Math.max(depth(root.left),depth(root.right))+1;
    }
}

但是这样是有重复计算的步骤在里面的，因为我们到最后的时候，如果遇到了不符合的情况，其实是是可以直接进行一个剪枝的操作的。所以优化的思路就是设置一个 -1 的情况，如果遇到了 -1 的情况，那就直接返回到上一层。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return recur(root)!=-1;
    }

    private int recur(TreeNode root) {

        if(root == null){
            return 0;
        }
        int left = recur(root.left);
        if(left == -1)return -1;
        int right = recur(root.right);
        if(right == -1)return -1;
        return Math.abs(left- right)<2?Math.max(left,right)+1:-1;
    }
}

100. 相同的树

这道题就是需要判断一下两个树是不是一样的。对于每一层来说，如果都是null的话，那就说明是一样的，如果有一个不是多话，那就false了。如果值不相等的话，失败。进入下一层。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

95. 不同的二叉搜索树 II

这道题和之前的那道题有一点不一样，第一个是他需要输出所有的可能的解。

二叉搜索树，都知道他的左子树需要小于他的根节点，而右子树需要大于他的根节点。这道题的思路就是我们吧[1…..n]的序列做一个拆分，遍历里面的节点。以i为例。[1…i-1][i][i+1….n]可以分为这三个序列。那么问题其实就变小了。我们可以递归的去求解里面的子序列。这就是一个典型的递归题目了。
对于每一个子节点，我们可以获得他的左子树和柚子树的集合。每次遍历哪一个出来搭起来就是我们的答案了。

递归的终止条件： left > right 这个时候说明这个序列是空的，需要加上一个null。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n ==0){
            return new LinkedList<TreeNode>();
        }
        return generrate(1,n);
    }

    private List<TreeNode> generrate(int left, int right) {
        List<TreeNode> allTree = new LinkedList<>();

        if(left>right){
            allTree.add(null);
            return allTree;
        }

        for (int i = left; i <=right; i++) {
            List<TreeNode> leftTree = generrate(left,i-1);
            List<TreeNode> rightTree = generrate(i+1,right);

            for(TreeNode l:leftTree){
                for (TreeNode r:rightTree){
                    TreeNode cur = new TreeNode(i);
                    cur.left = l;
                    cur.right = r;
                    allTree.add(cur);
                }
            }

        }
        return allTree;
    }
}

112. 路径总和

采用DFS的思路，递归下去，遇到该节点是子节点而且数值相同的情况下返回结果。

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        return dfs(root,sum,0);

    }

    private boolean dfs(TreeNode root, int target, int sum) {
        if(root == null) return false;
        sum += root.val;
        boolean left = false;
        boolean right = false;
        if(root.left==null && root.right==null && sum == target){
            return true;
        }
        if(root.left!=null){
             left = dfs(root.left,target,sum);
        }
        if(root.right!=null){
             right = dfs(root.right,target,sum);
        }
        return left||right;
    }
}

108. 将有序数组转换为二叉搜索树

思路：首先想一下如何建立一个树。把数组分成2部分，左边的和右边的。 mid就是root，递归建立相应的左右子树。这样可以保证这个高度差是1

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null) return null;

        return rebuild(nums,0,nums.length-1);
    }

    private TreeNode rebuild(int[] nums, int l, int r) {
        if(l>r) return null;
        int mid = l+(r-l)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = rebuild(nums,l,mid-1);
        root.right = rebuild(nums,mid+1,r);
        return root;

    }
}

124. 二叉树中的最大路径和

思路：
对于答案里面的节点，只有两种可能：
第一种是，他和左右子树的最大值+父节点
第二种的他连接左右子树。

class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }
    private int dfs(TreeNode root) {
        if(root ==null){
            return 0;
        }
        int leftMax = Math.max(0,dfs(root.left)); // 左子树的最大边
        int rightMax = Math.max(0,dfs(root.right));//  左子树的最大边
        max = Math.max(max,leftMax+rightMax+root.val); // 第二种情况的最大值
        return Math.max(leftMax,rightMax)+root.val;// 返回对答案最有帮助的数值。
    }
}

1028. 从先序遍历还原二叉树

思路：
当前的节点是S，前一个节点是P 只有两种可能，1. S是P的左节点，或者是根节点到S节点的某个节点的右节点。使用一个栈来记录一下路径。
参考：https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/solution/cong-xian-xu-bian-li-huan-yuan-er-cha-shu-by-leetc/

class Solution {
    public TreeNode recoverFromPreorder(String S) {
        Deque<TreeNode> path = new LinkedList<>();
        int pos = 0;

        while (pos<S.length()){
            int level = 0;
            while (pos<S.length()&&S.charAt(pos)=='-'){
                level++;
                pos++;
            }
            int val=0;
            while (pos<S.length()&&Character.isDigit(S.charAt(pos))){
                val = val*10+S.charAt(pos)-'0';
                pos++;
            }
            TreeNode node = new TreeNode(val);

            if (level==path.size()){
                if(!path.isEmpty()){
                    path.peek().left = node;
                }
            }else {
                while (path.size()>level){
                    path.pop();
                }
                path.peek().right = node;
            }
            path.push(node);
        }
        while (path.size()>1){
            path.pop();
        }
        return path.peek();
    }
}

236. 二叉树的最近公共祖先

一层一层的去搜索这个节点。
终止条件： root ==null 或者等于p或者q。
如果没有的话，那就往下一层搜索。
返回left和right结果。
如果都是null 说明没有找到，不在里面。
如果有一个null 说明在一边。那就是返回的哪个值。
如果都不是null，那就说明在两边的子树上。返回root

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root== null||root == p||root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right  = lowestCommonAncestor(root.right,p,q);

        if(left == null&&right == null){
            return null;
        }else if(left != null&&right != null){
            return root;
        }else{
            return left==null?right:left;
        }


    }
}

105. 从前序与中序遍历序列构造二叉树

前序的第一个数，就是这个的根。根据根节点，可以在中序的里面找到左子树和右子树两部分。因为要根据根节点来在中序里面做一个搜索，这个可以使用哈希表来做一个优化。值得注意的是，吧中序和前序的坐标分开来比较好。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 HashMap<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int left = 0;
        int right = preorder.length;

        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return rebuild(left,right,preorder,inorder,left,right);
    }

    private TreeNode rebuild(int p_left, int p_right, int[] preorder, int[] inorder, int i_left, int i_right) {
        if(p_left == p_right) return null;
        TreeNode root = new TreeNode(preorder[p_left]);
        int index = map.get(root.val);
        int leftNum = index - i_left;

        root.left = rebuild(p_left+1,p_left+leftNum+1,preorder,inorder,i_left,index);
        root.right = rebuild(p_left+leftNum+1, p_right,preorder,inorder, index+1, i_right);

        return root;

    }
}

297. 二叉树的序列化与反序列化

把二叉树变成字符串，之后再返回回来。主要诗递归来做。使用一个字符作为分隔，例如！。

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return  "#!";
        }
        String str = root.val+"!";
        str += serialize(root.left);
        str += serialize(root.right);
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] s = data.split("!");
        Queue<String> queue = new LinkedList<>();
        for(int i=0;i<s.length;i++){
            queue.add(s[i]);
        }

        return rebuild(queue);
    }

     private TreeNode rebuild(Queue<String> queue) {
        String str = queue.poll();
        if(str.equals("#")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(str));

        root.left = rebuild(queue);
        root.right = rebuild(queue);

        return root;
     }
}

111. 二叉树的最小深度

这道题的思路和上面的那道其实是一样的，就是需要注意的是怎么算才是一个最终的子节点。这莱恩算法就是所这个节点的左孩子和右孩子都是null 的时候，才算是。


class Solution {
    public int minDepth(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        int depth = 0;

        if(root == null) return depth;

        queue.add(root);
        while (!queue.isEmpty()){
            depth++;
            int size = queue.size();

            for(int i=0;i<size;i++){
                TreeNode tmp = queue.poll();
                if(tmp.left ==null&&tmp.right==null){
                    return depth;
                }
                if(tmp.left!=null){
                    queue.add(tmp.left);
                }
                if(tmp.right!=null){
                    queue.add(tmp.right);
                }


            }
        }
        return depth;
    }
}

104. 二叉树的最大深度

给你一棵树，说的他的最大深度。诗递归来做，每一层递归的时候吧深度+1，递归左右两个子树。

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int res = finMaxDepth(0,root);
        return res;

    }
    private int finMaxDepth(int depth,TreeNode root){
        if(root == null) return depth;

        return Math.max(finMaxDepth(depth+1,root.left),finMaxDepth(depth+1,root.right));
    }
}

第二种思路我们可以借助一个队列，就像是逐层的遍历这个二叉树。妹子遍历，都把depth+1。

class Solution {
    public int maxDepth(TreeNode root) {
                Queue<TreeNode> queue = new LinkedList<>();

        int depth = 0;
        if(root == null){
            return depth;
        }

        queue.add(root);
        while(!queue.isEmpty()){
            depth++;
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode tmp = queue.poll();
                if(tmp.left!=null){
                    queue.add(tmp.left);
                }
                if(tmp.right!=null){
                    queue.add(tmp.right);
                }
            }

        }
        return  depth;

    }
}

226. 翻转二叉树

给你两棵树，做一个镜像翻转。其实哦我们考虑这是一个一层一层的镜像翻转。每层的节点做一个交换。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        reverse(root);
        return root;

    }
    private void reverse(TreeNode root){
        if(root ==null){
            return;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        reverse(root.left);
        reverse(root.right);
    }
}

572. 另一个树的子树

给定两个树，判断一下，T是不是S的子树。
遇到树的题目，第一个想到的事情就是使用一个递归函数来表示。

所以我们需要一个isSame 的函数来表示一下。对视isSame函数。如果两个节点都是null，那说明递归到了最下层了。是对的。只要其中一个是null，就说明不是一个子树。

对于isSUbTree 函数来说。需要找到对应的开始节点。如果t==null 这是子树。如果s==null 说明已经递归到最后面了，不是子树。

接着把这个节点的子节点和当前的节点分别放入issame函数。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s==null)return false;
        if(t==null)return true;


        return isSubtree(s.right,t)||isSubtree(s.left,t)||isSame(s,t);


    }
    private boolean isSame(TreeNode s,TreeNode t){
        if(s== null&&t==null){
            return true;
        }
        if(s==null||t==null){
            return false;
        }
        if(s.val == t.val){
            return isSame(s.right,t.right)&&isSame(s.left,t.left);
        }else{
            return false;
        }
    }
}

98. 验证二叉搜索树

想一下中序遍历的情况，直接吧这个结果放到一个数组里面。判断一下是不是大小依次排好的就可以。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
       if(root == null){
            return  true;
        }
        inorder(root);
        for(int i=1;i<res.size();i++){
            if(res.get(i)<=res.get(i-1)){
                return false;
            }
        }
        return true;

    }

    private void inorder(TreeNode root) {
        if(root !=null){
            inorder(root.left);
            res.add(root.val);
            inorder(root.right);
        }
    }
}

思路2：采用中序遍历的样子，但是保留一个之前的数。只要这个数比pre还要小的话就直接跳出。

long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        if(!isValidBST(root.left)){
            return false;
        }
        if(root.val<=pre){
            return false;
        }

        pre = root.val;
        return isValidBST(root.right);

    }

94. 二叉树的中序遍历

思路：可以使用递归来实现，题目要求我们试一下使用循环来写。这其实在要求我们维护一个栈来实现遍历。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root);
        return res;


    }
    private void inorder(TreeNode root){
        if(root!=null){
            inorder(root.left);
            res.add(root.val);
            inorder(root.right);
        }
    }
}

还有一种方法，可以让这个节点带有颜色，使得思路更加的清晰。前中后的遍历代码统一。
具体来说，我们需要标记一下这是第一次进来还是第二次进来。如果是第二次进来的话，就添加到res里面去。如果不是的话，把他的右节点，左节点也加入到里面去。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    class ColorNode{
        TreeNode node;
        boolean hasVisit;
        public ColorNode(TreeNode root,boolean c){
            node = root;
            hasVisit = c;
        }

    }
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<>();

        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();

        stack.push(new ColorNode(root,false));

        while(!stack.isEmpty()){
            ColorNode tmp = stack.pop();

            if(!tmp.hasVisit){
                if(tmp.node.right!=null){
                    stack.push(new ColorNode(tmp.node.right,false));
                }
                stack.push(new ColorNode(tmp.node,true));
                if(tmp.node.left!=null){
                    stack.push(new ColorNode(tmp.node.left,false));
                }
            }else{
                res.add(tmp.node.val);
            }
        }
        return res;

    }
}

144. 二叉树的前序遍历

和中序遍历是一样的，就是代码调换一下顺序。

并查集

并查集是一个指向自己父节点的数据结构，主要的操作有 find，查找这个节点的父节点。
union 把两个集合融合在一起。
isConnected 判断是不是连接、
说一下里面的路径压缩。并查集如果不进行路径压缩的话，可能的问题就是这个并查集会退化成为一个链表一样的结构。路径压缩思路如下：

        public int find(int x){
            while (x!=parent[x]){
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

990. 等式方程的可满足性

总体的阶梯思路如下：

class Solution {
    public boolean equationsPossible(String[] equations){
        UnionFind uniondfind = new UnionFind(26);

        for(String s:equations){
            char[] charArray = s.toCharArray();
            if(charArray[1] == '='){
                int index1 = charArray[0]-'a';
                int index2 = charArray[3]-'a';
                uniondfind.union(index1,index2);
            }
        }

        for(String s:equations){
            char[] charArray = s.toCharArray();
            if(charArray[1] == '!'){
                int index1 = charArray[0]-'a';
                int index2 = charArray[3]-'a';
                if(uniondfind.isConnected(index1,index2)){
                    return false;
                }
            }
        }
        return true;

    }
    private class UnionFind{
        private int[] parent;
        public UnionFind(int x){
            parent = new int[x];
            for (int i=0;i<parent.length;i++){
                parent[i] = i;
            }
        }
        public int find(int x){
            while (x!=parent[x]){
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        public void union(int x,int y){
            int index1 = find(x);
            int index2 = find(y);
            parent[index1] = index2;
        }
        public boolean isConnected(int x,int y){
            return find(x) == find(y);
        }
    }
}