剑指Offer之Java算法习题精讲二叉树专项训练

/**

  * 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 {

     int i = 0 ;

     int res = 0 ;

     public int kthSmallest(TreeNode root, int k) {

         method(root,k);

         return res;

     }

      public void method(TreeNode root, int k){

         if (root== null ) return ;

         method(root.left,k);

         i++;

         if (i==k){

             res = root.val;

             return ;

         }

         method(root.right,k);

      }

}

/**

  * 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 {

     int sum = 0 ;

     public TreeNode convertBST(TreeNode root) {

         method(root);

         return root;

     }

     public void method(TreeNode root) {

         if (root== null ){

             return ;

         }

         method(root.right);

         sum+=root.val;

         root.val = sum;

         method(root.left);

     }

}

/**

  * 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 isValidBST(TreeNode root) {

         return method(root, null , null );

     }

     public boolean method(TreeNode root,TreeNode min,TreeNode max){

         if (root== null ) return true ;

         if (min!= null &&root.val<=min.val) return false ;

         if (max!= null &&root.val>=max.val) return false ;

         return method(root.left,min,root)&&method(root.right,root,max);

     }

}

/**

  * 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 TreeNode searchBST(TreeNode root, int val) {

         if (root== null ) return null ;

         if (root.val==val) return root;

         if (root.val>=val){

             return searchBST(root.left,val);

         }

         if (root.val<val){

             return searchBST(root.right,val);

         }

         return 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 TreeNode insertIntoBST(TreeNode root, int val) {

         return   method(root,val);

     }

     public TreeNode method(TreeNode root, int val){

         if (root== null ) return new TreeNode(val);

         if (root.val < val)

             root.right = insertIntoBST(root.right, val);

         if (root.val > val)

             root.left = insertIntoBST(root.left, val);

         return root;

     }

}

/**

  * 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 TreeNode deleteNode(TreeNode root, int key) {

         if (root == null ) return null ;

         if (root.val == key){

             if (root.left == null ) return root.right;

             if (root.right == null ) return root.left;

             TreeNode minNode = getMin(root.right);

             root.right = deleteNode(root.right, minNode.val);

             minNode.left = root.left;

             minNode.right = root.right;

             root = minNode;

         } else if (root.val>key){

             root.left = deleteNode(root.left,key);

         } else {

             root.right = deleteNode(root.right,key);

         }

         return root;

     }

     TreeNode getMin(TreeNode node) {

         while (node.left != null ) node = node.left;

         return node;

     }  

}