树型算法题解

痛定思痛。 2023-07-18 09:47 12阅读 0赞

##### 树结构如下 #####

public class TreeNode { 
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) {  val = x; }
      }

##### 1. 获取给定二叉树最小深度 #####

思路：通过广度优先遍历能更快找到最优解。深度优先搜索也可以找到最优解，但是需要找到所有解后

###### 广度优先搜索,一层一层搜索，搜索到某个节点左右节点都为空，则为叶子结点。缺点是相对比较占空间，需要用一个`队列`记录下一次要搜索的节点。每层搜索完层数+1。 ######

import java.util.LinkedList;
    public class Solution {   
        public int run(TreeNode root) { 
             if (root == null) { 
                return 0;
            }
            LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(root);
            int level = 1,start = 0,end=1;
            while (!queue.isEmpty()) { 
                TreeNode temp = queue.remove();
                start ++;
                if (temp.left == null && temp.right == null) { 
                    return level;
                }
                if (temp.left != null) { 
                    queue.add(temp.left);
                }
                if (temp.right != null) { 
                    queue.add(temp.right);
                }
                if (start == end){ 
                    start = 0;
                    end = queue.size();
                    level ++;
                }
            }
            return level;
        }
    }

###### 深度优先搜索，搜索每个路径的深度，通过比较获得最小路径。通过`递归或栈`实现。需要注意一个特殊的情况，如果某个节点只有左节点或者只有右节点，应该统计有节点的那条路径，没有节点的那路径相当于没有叶子节点，不能用那个路径统计。 ######

public class Solution { 
        public int run(TreeNode root) { 
            if (root == null) { 
                return 0;
            }        
            if (root.left == null && root.right == null) { 
                return 1;
            }
            int leftDept = run(root.left);
            int rightDept = run(root.right);
            if (leftDept == 0 || rightDept == 0){ 
                return leftDept + rightDept + 1;
            }
            return leftDept < rightDept? leftDept+1 : rightDept+1; 
        }
    }

##### 2. 获取给定二叉树的后序遍历 #####

思路：通过`递归或栈`实现。

###### 递归,递归到左子树最深处。从底往上搜，先搜左子树，再搜右子树，再把当前节点加入集合。 ######

public class Solution { 
        ArrayList<Integer> list = new ArrayList<>();
        public ArrayList<Integer> postorderTraversal(TreeNode root) { 
            if (root == null){ 
                return list;
            }
            if (root.left == null && root.right == null){ 
                list.add(root.val);
                return list;
            }
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            list.add(root.val);
            return list;
        }
        
    }

###### 栈实现，可以通过Stack实现。 ######

**1. 先加入跟节点，根据跟节点遍历子节点，因为是后序遍历，所以父节点先不出栈，通过peek方法获取栈顶，但是不出栈  
2. 先让右节点进栈，因为左节点要先出栈。  
3. 暂存上一个出栈的节点，判断如果上一个节点是当前节点的子节点，即可出栈。因为子节点都是后进栈的，所以判断是任意一个子节点出栈，都代表当前可以出栈了（考虑有可能某个方向的节点为空，不然直接判断上一节点为右节点就好了）。  
4. 如果没有子节点也可以直接出栈了。**

public class Solution { 
        ArrayList<Integer> list = new ArrayList<>();
        public ArrayList<Integer> postorderTraversal(TreeNode root) { 
            if (root == null){ 
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);    
            TreeNode preNode = null;
            while (!stack.empty()){ 
                TreeNode node = stack.peek();
                if ((node.left == null && node.right == null)||
                    ( preNode !=null && (preNode == node.left || preNode == node.right))){ 
                    list.add(node.val);
                    stack.pop();
                    preNode = node;
                }else{ 
                    if (node.right !=null){ 
                        stack.push(node.right);
                    }
                    if (node.left !=null){ 
                        stack.push(node.left);
                    }
                }         
            }
            return list;
        } 
    }

##### 3. 获取给定二叉树的先序遍历 #####

思路： 通过递归或栈实现。

###### 通过递归实现，先将当前节点加入集合，再搜索左子树，再搜索右子树。 ######

public class Solution { 
        ArrayList<Integer> list =  new ArrayList<>();
        public ArrayList<Integer> preorderTraversal(TreeNode root) { 
            if (root == null){ 
                return list;
            }
            list.add(root.val);
            if (root.left == null && root.right == null){ 
                return list;
            }
            preorderTraversal(root.left);
            preorderTraversal(root.right);
            return list;
        }
    }

###### 通过栈实现,先入栈根节点，出栈后加入集合，再入栈右节点，再入栈左节点。根据后进先出，左节点会先搜索。 ######

public class Solution { 
        ArrayList<Integer> list =  new ArrayList<>();
        public ArrayList<Integer> preorderTraversal(TreeNode root) { 
            if (root == null){ 
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.empty()){ 
                TreeNode node = stack.pop();
                list.add(node.val);
                if (node.right != null){ 
                   stack.push(node.right);
                }
                if (node.left != null){ 
                   stack.push(node.left);
                }   
            }
            return list;
        }
    }

##### 4. 获取给定二叉树的中序遍历 #####

##### 5. 二叉树的值为0-9，获取根节点到所有子节点的所有路径表示的数字和。比如二叉树有两个路径，1->2->3和 1->4->5 那么获取到的值为 123 + 145。 #####

思路： 通过`递归`实现。路径值连成数，可以通过将上一个节点的值`*10 + 当前节点的值`实现。判断到`左右节点都为空，说明为叶子节点`，返回统计后的值。判断到节点为空，所以遍历到一个`空节点`，当前位置非叶子节点，`直接返回0`，取消这条路径的累积。将`各路径到达叶子节点统计的数相加`，得到结果。

public class Solution { 
        public int sumNumbers(TreeNode root) { 
            return sum(root,0);
        }
        public int sum(TreeNode root,int num){ 
            if (root == null){ 
                return 0;
            }
            int n = num * 10 + root.val;
            if (root.left == null && root.right == null){ 
                return n;
            }
            return sum(root.left,n) + sum(root.right,n);
        }
    }

##### 6. 求给定二叉树任意两个节点连起来，节点值总和最大是多少。起始节点和结束节点可以是任意节点，节点的值可以是负数。 #####

思路：通过递归实现。

1.  求任意节点连线最大，也可以看成是找到一个点，这个点到左子树的某个位置的值总和，加上这个点到右子树的某个位置的值总和，加上当前点的值，加起来最大。
2.  根节点可以是任意节点，所以在每次计算左右子树的路径的总和后，都要判断左右子树节点值总和的最大值是不是负的，不是负的则加上当前节点的值去跟最大值比较，如果比最大值大，则替换最大值。
3.  在方法返回时，也就是返回给树的上一层时，要判断当前节点的左右子树的节点值总和是不是负数，不是负数则加上两边比较大的返回，是直接返回当前节点的值。

import java.util.*;
    import java.math.*;
    public class Solution { 
        int max = Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) { 
            if(root == null) { 
                return 0;
            }
            getMax(root);
            return max;
        } 
        public int getMax(TreeNode node){ 
            if (node == null){ 
                return 0;
            }
            int num = node.val;
            int left = getMax(node.left);
            int right = getMax(node.right); 
            num = Math.max(num+left,num);
            num = Math.max(num+right,num);
            max = num>max? num: max;
            return Math.max(left,right)>0?node.val+Math.max(left,right):node.val;
        }
    }

##### 7. 假设现在有个完美二叉树，将所有节点的next指向右兄弟节点，右兄弟即相邻的右节点，包括非同个父亲节点。 #####

public class TreeLinkNode { 
          int val;
          TreeLinkNode left, right, next;
          TreeLinkNode(int x) {  val = x; }
      }

思路：

1.  递归遍历节点，判断左右子节点都不为空，则将左节点指向右节点。
2.  由于父亲节点比子节点先遍历，而且是`完美二叉树`，所以如果当前节点有右兄弟节点则next不为空，根据这点，可以将右子节点指向当前节点的右兄弟节点的左子节点。

public class Solution { 
        public void connect(TreeLinkNode root) { 
            if (root == null){ 
                return;
            }
            if (root.right != null && root.left!=null){ 
                root.left.next = root.right;
            }
            if (root.next!=null && root.next.left!=null && root.right!=null){ 
                root.right.next = root.next.left;
            }
            connect(root.left);
            connect(root.right);
        }
    }

##### 8. 与第7题目一样，但是二叉树是普通二叉树，不是完美二叉树 #####

思路：

1.  由于不是完美二叉树，所以不能直接依赖将当前节点的左节点连到右节点，有可能当前左节点不为空，右节点为空，但是右兄弟节点的左节点不为空，这时是需要将当前节点的左节点连接到右兄弟节点的左节点的。所以不能按照第7题求解
2.  可以一层一层遍历，每层节点的next连接依靠遍历上一层节点去连接。
3.  可以定义一个头节点，用于将整一层的节点连接成一条链表，然后下一层直接遍历这条链表，对链表上每个节点的左右节点进行判断，不为空则将next连接起来。相当于完成了next的连接，又记录一层的链表。
4.  一层层遍历可直接使用循环遍历，或者用递归遍历。

**递归**

public class Solution { 
        public void connect(TreeLinkNode root) { 
            if (root == null){ 
                return;
            }
            // 定义头节点用于连接下一层
            TreeLinkNode head = new TreeLinkNode(-1);
            // 定义临时节点用于链表连接
            TreeLinkNode temp = head;
            // 根据当前层的链表 遍历当前层的节点
            for (TreeLinkNode node=root;node!=null;node=node.next){ 
                // 将下一层的节点用next连起来 形成链表
                if (node.left!=null){ 
                    temp.next=node.left;
                    temp=temp.next;
                }
                if (node.right!=null){ 
                    temp.next=node.right;
                    temp=temp.next;
                }
            }
            // 处理连接好的下一层
            connect(head.next);
        }
    }

循环

public class Solution { 
        public void connect(TreeLinkNode root) { 
            while(root!=null){ 
                // 定义头节点用于连接下一层
                TreeLinkNode head = new TreeLinkNode(-1);
                TreeLinkNode temp = head;
                for (TreeLinkNode node=root;node!=null;node=node.next){ 
                    if (node.left!=null){ 
                        temp.next=node.left;
                        temp=temp.next;
                    }
                    if (node.right!=null){ 
                        temp.next=node.right;
                        temp=temp.next;
                    }
                }
                root=head.next;
            }
        }
    }

##### 9. 判断是否有从根节点到叶子节点的节点值之和等于sum的路径， #####

思路：因为需要走到叶子节点才可以得到结果，因此采用深度优先搜索，搜到一个匹配就直接返回true，不用搜索其他路径了，可以用||，左边为true右边就不会执行了。

public class Solution { 
        int sum;
        public boolean hasPathSum(TreeNode root, int sum) { 
            this.sum = sum;
            return has(root, 0);
        }
        // 定义一个值用于计算路径总和
         public boolean has(TreeNode node,int number){ 
           if(node ==null){ 
               return false;
           }
           number += node.val;
           
           if (node.left==null && node.right==null) { 
              return number==sum;
           }
           // 从左往右搜，搜到了右边还没搜的就不会走了
           return has(node.left,number)|| has(node.right, number);
         }
    }

##### 10.给定一个二叉树和一个值sum，找出所有的根节点到叶子节点的节点值之和等于sum的路径， #####

思路：用递归实现。

1.  记录路径和节点和可以通过方法递归传递。
2.  判断如果是叶子节点了，则将节点值之和和给定的sum比较，如果匹配则把节点记录的路径加入结果集。需要注意要`重新创建一个list对象`再放入结果集。因为算到叶子节点后，`要把记录路径的集合去掉当前节点`，这样回溯到上一层遍历的时候，集合里的路径就不会把当前节点算进去。
3.  如果不是叶子节点，则先把左右子树的节点遍历结束，等左右子树都搜完了，就没必要保留当前节点了，需要搜索其他路径了。所以把当前节点从路径记录中删除，回溯到上一层。
4.  两个删除节点的地方，因为当前路径都是路径集合的最后一个位置，所以删除集合最后一个节点即可。

import java.util.*;
    public class Solution { 
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int sum;
        public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) { 
            this.sum=sum;
            pathSum(root,0,new ArrayList<Integer>());
            return result;
        }
        public void pathSum(TreeNode node,int num,ArrayList<Integer> path){ 
            if (node == null){ 
                return;
            }
            path.add(node.val);
            num += node.val;
            if (node.left==null && node.right==null){ 
                if (num == sum){ 
                    result.add(new ArrayList(path));
                }
                path.remove(path.size()-1);
                return;
            }
            pathSum(node.left,num,path);
            pathSum(node.right,num,path);
            path.remove(path.size()-1);
        }
    }

##### 11.判断二叉树是否为平衡二叉树,定义平衡二叉树为每个节点的左右两个子树高度差的绝对值不超过1的二叉树 #####

思路：

1.  因为要满足每个节点的树高度差不超过一，所以从上往下，求出每个节点左右子树的高度，如果判断节点高度超过1了，就不用求其他节点了。
2.  分两个方法，一个方法用于获取当前节点的高度，求高度通过递归+1实现，因为需要获取的是高度，所以要获取最长路径。
3.  另一个方法用递归遍历所有节点，判断所有节点都满足高度差不超过1，则可判断出是平衡二叉树。

import java.math.*;
    public class Solution { 
        public boolean isBalanced(TreeNode root) { 
            if(root==null)
                return true;
            if(Math.abs(getDepth(root.left)-getDepth(root.right))>1){ 
                return false;
            }
            return isBalanced(root.left)&&isBalanced(root.right);
        }
        public int getDepth(TreeNode node){ 
            return node==null?0:Math.max(getDepth(node.left),getDepth(node.right))+1;
        }
    }

##### 12.返回二叉树由底层到顶层的层序遍历，（从左向右，从叶子节点到根节点，一层一层的遍历）。 #####

思路一：从顶层往底层遍历，每层遍历的结果都放在list的头部，实现最终顶层在后面，底层在前面。层序遍历可以通过外循环一层层往下遍历，用一个集合记录下一层的节点，内循环遍历这一个集合实现。

import java.util.*;
    public class Solution { 
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) { 
            if (root == null){ 
                return result;
            }
            List<TreeNode> list = new ArrayList<>();
            list.add(root);
            levelOrderBottom(list);
            return result;
        }
        public void levelOrderBottom(List<TreeNode> levelNodeList) { 
            if (levelNodeList.isEmpty()){ 
                return;
            }
            List<TreeNode> nextLevelNodeList = new ArrayList<>();
            ArrayList<Integer> levelPath = new ArrayList<>();
            for (TreeNode node:levelNodeList){ 
                if(node.left!=null){ 
                    nextLevelNodeList.add(node.left);
                }
                if (node.right!=null){ 
                    nextLevelNodeList.add(node.right);
                }
                levelPath.add(node.val);
            }
            result.add(0,levelPath);
            levelOrderBottom(nextLevelNodeList);
        }
    }

思路二（`优化`）：与思路一类似，但是不每次都添加到集合的首部，因为涉及到`数组复制`，可以考虑先递归到底层，再不断回溯加到结果集，实现底部先加入结果集。`与思路基本一样，只是最后两行代码换顺序`

import java.util.*;
    public class Solution { 
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) { 
            if (root == null){ 
                return result;
            }
            List<TreeNode> list = new ArrayList<>();
            list.add(root);
            levelOrderBottom(list);
            return result;
        }
        public void levelOrderBottom(List<TreeNode> levelNodeList) { 
            if (levelNodeList.isEmpty()){ 
                return;
            }
            List<TreeNode> nextLevelNodeList = new ArrayList<>();
            ArrayList<Integer> levelPath = new ArrayList<>();
            for (TreeNode node:levelNodeList){ 
                if(node.left!=null){ 
                    nextLevelNodeList.add(node.left);
                }
                if (node.right!=null){ 
                    nextLevelNodeList.add(node.right);
                }
                levelPath.add(node.val);
            }
            levelOrderBottom(nextLevelNodeList);
            result.add(levelPath);
        }
    }

##### 13.给出一棵树的中序遍历和后序遍历，请构造这颗二叉树。假定给出的树中不存在重复的节点。 #####

中序：父节点在中间，左子树节点都在右子树节点前面  
后序：父节点在后，左子树节点都在右子树节点前面  
**思路:**

1.  由于后序遍历最后一个值为根节点，根据根节点可以把中序遍历分成左子树的节点和右子树的节点
2.  此时可以知道左子树的节点数量，根据这个节点数量，可以把后序遍历的节点也分成左子树节点和右子树节点。
3.  此时可以先构建出根节点，开始填充根节点的左右节点，根据1、2点的规则把中序遍历和后序遍历分成左右子树递归处理。

public class Solution { 
        int[] inorder;
        int[] postorder;
        public TreeNode buildTree(int[] inorder, int[] postorder) { 
            if (inorder.length==0 || postorder.length==0){ 
                return null;
            }
            this.inorder=inorder;
            this.postorder=postorder;
            return buildTree(0,inorder.length-1,0,postorder.length-1);
        }
        public TreeNode buildTree(int inStart,int inEnd,int postStart,int postEnd) { 
            if (inStart>inEnd || postStart>postEnd){ 
                return null;
            }
            // 中序遍历中间节点的下标
            int index=0;
            // 遍历中序遍历数组 找头节点位置
            for (int i=inStart;i<=inEnd;i++){ 
                // 后序遍历尾节点为头节点
                if (inorder[i]==postorder[postEnd]){ 
                    index=i;
                    break;
                }
            }
            // 跟起始位置相减 得到左子树的节点数
            // index是当前子树的中间节点在整个数组的下标，当前如果递归到子树，需要减去子树的起始下标才是当前子树的左子树的节点数
            int leftNodeSize=index-inStart;
            
            TreeNode node = new TreeNode(postorder[postEnd]);
            // 获取左节点 计算中序遍历和后序遍历左子树节点的下标
            // postStart+leftNodeSize-1 根据左节点数加上后序遍历的子树的起始下标，-1得到左子树最后一个节点的下标
            node.left = buildTree(inStart,index-1,postStart,postStart+leftNodeSize-1);
            // 获取左节点 计算中序遍历和后序遍历拆成右子树节点的下标
            node.right = buildTree(index+1,inEnd,postStart+leftNodeSize,postEnd-1);
            return node;
        }
    }

##### 14. 给出一棵树的前序遍历和中序遍历，请构造这颗二叉树。假定给出的树中不存在重复的节点。 #####

前序：父节点在前，左子树节点都在右子树节点前面  
中序：父节点在中间，左子树节点都在右子树节点前面

**思路：**  
与第13题类似，前序遍历首节点即为根节点，通过根节点找到在中序遍历的位置，中序遍历分为左右子树，根据左右子树的大小，可以把前序遍历分成左右子树。递归处理。

public class Solution { 
         int[] inorder;
        int[] preorder;
        public TreeNode buildTree(int[] preorder, int[] inorder) { 
            if (inorder.length==0 || preorder.length==0){ 
                return null;
            }
            this.inorder=inorder;
            this.preorder=preorder;
            return buildTree(0,inorder.length-1,0,preorder.length-1);
        }
        public TreeNode buildTree(int inStart,int inEnd,int preStart,int preEnd) { 
            if (inStart>inEnd || preStart>preEnd){ 
                return null;
            }
            int index=0;
            // 遍历中序遍历数组 找头节点位置
            for (int i=inStart;i<=inEnd;i++){ 
                // 后序遍历尾节点为头节点
                if (inorder[i]==preorder[preStart]){ 
                    index=i;
                    break;
                }
            }
            // 跟起始位置相减 得到左子树的节点数
            int leftNodeSize=index-inStart;
            TreeNode node = new TreeNode(preorder[preStart]);
            // preStart+leftNodeSize 起始位置加上左子树节点数刚好得到在前序遍历的下标，因为头节点在前面，要向右偏移1，+1 -1刚好抵消
            node.left = buildTree(inStart,index-1,preStart+1,preStart+leftNodeSize);
            node.right = buildTree(index+1,inEnd,preStart+leftNodeSize+1,preEnd);
            return node;
        }
    }

##### 15.求给定二叉树的最大深度，最大深度是指树的根结点到最远叶子结点的最长路径上结点的数量。 #####

思路：比较简单，递归二叉树，取大的分支节点数就好。

import java.math.*;
    public class Solution { 
        public int maxDepth(TreeNode root) { 
           if (root==null){ 
               return 0;
           }
           return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
        }
    }

##### 16.给定一个二叉树，返回该二叉树的之字形层序遍历，（从左向右，下一层从右向左，一直这样交替 #####

思路：层序遍历，然后用一个标记决定路径是往前加还是从后面加。

import java.util.*;
    public class Solution { 
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int count=1;
        public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { 
            if (root == null){ 
                return result;
            }
            List<TreeNode> list = new ArrayList<>();
            list.add(root);
            zigzagLevelOrder(list);
            return result;
        }
        public void zigzagLevelOrder(List<TreeNode> levelNodeList) { 
            if (levelNodeList.isEmpty()){ 
                return;
            }
            List<TreeNode> nextLevelNodeList = new ArrayList<>();
            ArrayList<Integer> levelPath = new ArrayList<>();
            for (TreeNode node:levelNodeList){ 
                    if(node.left!=null){ 
                        nextLevelNodeList.add(node.left);
                    }
                    if (node.right!=null){ 
                        nextLevelNodeList.add(node.right);
                    }
                    if (count%2!=0){ 
                        levelPath.add(node.val);
                    }else{ 
                        levelPath.add(0,node.val);
                    }
            }
            count++;
            result.add(levelPath);
            zigzagLevelOrder(nextLevelNodeList);
        }
    }

##### 17. 给定一棵二叉树，判断琪是否是自身的镜像（即：是否对称） #####

思路：递归实现，左孩子的左孩子节点要跟右孩子的右孩子相等，左孩子的右孩子要和右孩子的左孩子相等。

public class Solution { 
        public boolean isSymmetric(TreeNode root) { 
            if (root == null){ 
                return true;
            } 
            return isSymmetric(root.left,root.right);
        }
        public boolean isSymmetric(TreeNode left,TreeNode right) { 
            if (left==null && right==null){ 
                return true;
            }
            if (left==null || right==null){ 
                return false;
            }
            return left.val==right.val && isSymmetric(left.left,right.right)
                && isSymmetric(left.right,right.left);
        }
    }

##### 18.给出两个二叉树，请写出一个判断两个二叉树是否相等的函数。 #####

思路：递归每个节点判断

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

##### 19.判断给出的二叉树是否是一个二叉搜索树（BST） #####

思路：基于中序遍历实现，前一个节点的值要小于后一个节点，可以通过栈实现，左节点遍历结束才开始判断当前节点，然后遍历右节点。遍历右节点后同样先遍历完左节点，递归处理。

方法一：通过栈实现，将左孩子进栈，直到最左孩子为空，开始出栈，并处理开始处理右孩子。

import java.util.*;
    public class Solution { 
        public boolean isValidBST(TreeNode root) { 
            if (root==null){ 
                return true;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode pre=null;
            TreeNode cur=root;
            // 判断cur不为空是因为可能栈已经空了，但是右孩子还没开始处理
            while (!stack.isEmpty() || cur!=null){ 
                if (cur==null){ 
                    cur = stack.pop();
                    if (pre!=null && cur.val<=pre.val){ 
                        return false;
                    }
                    pre=cur;
                    cur=cur.right;
                }else{ 
                    stack.push(cur);
                    cur=cur.left;
                }
            }
            return true;
        }
    }

方法二，通过递归实现

public class Solution { 
        // pre记录上一次遍历的节点
        TreeNode pre = null;
        public boolean isValidBST(TreeNode root) { 
            if (root==null){ 
                return true;
            }
            // 先递归到最左孩子
            if (!isValidBST(root.left)){ 
                return false;
            }
            // 开始跟上一个节点判断
            if (pre!=null && pre.val>=root.val){ 
                return false;
            }
            pre=root;
            // 开始递归右孩子
            return isValidBST(root.right);
        }
    }

##### 20.二叉搜索树（BST）中的两个节点被错误地交换了，请在不改变树的结构的情况下恢复这棵树。 #####

public class Solution { 
        TreeNode pre = null;
        TreeNode p = null;
        TreeNode q = null;
        public void recoverTree(TreeNode root){ 
            if (root==null){ 
                return;
            }
             dfs(root);
             int temp = p.val;
             p.val=q.val;
             q.val=temp;
        }
        
        public void dfs(TreeNode root) { 
            if (root==null){ 
                return;
            }
            dfs(root.left);
            if (pre!=null && pre.val>root.val){ 
                if (p==null){ 
                    p=pre;
                }
                q=root;       
            }
            pre=root;
            dfs(root.right);
        }
    }

##### 21.给定一个值n，能构建出多少不同的值包含1…n的二叉搜索树（BST）？ #####

思路：  
fun(1)=1;  
fun(2)=fun(1)\*fun(0)+fun(0)\*fun(1);  
fun(3)=fun(2)\*fun(0)+fun(1)\*fun(1)+fun(0)\*fun(2);  
左子树和右子树的节点数不一样，排列方式也不一样，总的二叉树组成方式总数，左子树各种节点数和右子树各种节点数的二叉搜索树个数相乘，最后相加即可得出。  
通过递归，设定fun(0)=1即可得解。

递归实现：

public class Solution { 
        public int numTrees(int n) { 
            if (n==0 || n==1){ 
                return 1;
            }
            int sum=0;
            for (int j=1;j<=n;j++){ 
                sum += numTrees(j-1)*numTrees(n-j);
            }
            return sum;
        }
    }

由于递归写法需要重复计算，小于n的某种情况的值，所以可以通过数组记录中间值。

public class Solution { 
        public int numTrees(int n) { 
           int[] sum = new int[n+1];
           sum[0]=1;
           sum[1]=1;
           return numTrees(n,sum);
        }
        
        public int numTrees(int n,int sum[]){ 
            if (sum[n]!=0){ 
                return sum[n];
            }
            for (int j=1;j<=n;j++){ 
                sum[n] += numTrees(j-1,sum)*numTrees(n-j,sum);
            }
            return sum[n];
        }
    }

还可以通过加上一层循环替换递归。

public class Solution { 
        public int numTrees(int n) { 
           int[] sum = new int[n+1];
           sum[0]=1;
           sum[1]=1;
           for (int i=2;i<=n;i++){ 
               for (int j=1;j<=i;j++){ 
                  sum[i] += sum[j-1] * sum[i-j];
               }
           }
           return sum[n];
        }
    }

##### 22.给定一个值n,请生成所有的存储值1…n.的二叉搜索树（BST）的结构 #####

思路：因为是1…n，是连续的数，不用考虑搜索树的特性，只要考虑将节点分成不同节点数给左右子树，且递归往下分配即可。  
通过递归和三层循环实现。

1.  第一层循环负责给左右子树分节点，比如1-3用（左子树节点数,右子树节点数），可以分成(0,2)(1,1)(2,0)三种。而子树同理也可以将它的左右子树节点数进行分配，进而得到不同的组合方式，因此可以通过递归获取子树的组合方式集合。
2.  第二层和第三层循环是将左子树和右子树各种组合方式进行组合，从而得到所有情况的组合。

import java.util.*;
    public class Solution { 
        public ArrayList<TreeNode> generateTrees(int n) { 
            return build(1,n);
        }
        
        public ArrayList<TreeNode> build(int start,int end){ 
            ArrayList<TreeNode> curList = new ArrayList<>();
            if (start>end){ 
                curList.add(null);
                return curList;
            }
            for (int i=start;i<=end;i++){ 
                ArrayList<TreeNode> leftList = build(start,i-1);
                ArrayList<TreeNode> rightList = build(i+1,end);
                for (int j=0;j<leftList.size();j++){ 
                    for (int k=0;k<rightList.size();k++){ 
                        TreeNode node = new TreeNode(i);
                        node.left = leftList.get(j);
                        node.right = rightList.get(k);
                        curList.add(node);
                    }
                }
            }
            return curList;
        }
    }