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

剑指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;

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

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 foHWtxkXmxjVr 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;

}

}

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 foHWtxkXmxjVr 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;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。