654. 最大二叉树
题目连接：https://leetcode.cn/problems/maximum-binary-tree/
思路：使用前序构建二叉树 区间[left, right)
/**
* 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 {
private TreeNode constructMaximumBinaryTree(int[] nums, int left, int right) {
if (left >= right) return null;
// if (right - left == 1) return new TreeNode(nums[left]);
int maxIndex = left;
for (int i = left + 1; i < right; i++) {
if (nums[i] > nums[maxIndex]) {
maxIndex = i;
}
}
int val = nums[maxIndex];
TreeNode treeNode = new TreeNode(val);
treeNode.left = constructMaximumBinaryTree(nums, left, maxIndex);
treeNode.right = constructMaximumBinaryTree(nums, maxIndex + 1, right);
return treeNode;
}
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums == null || nums.length == 0) return null;
return constructMaximumBinaryTree(nums, 0, nums.length);
}
}
二、 617. 合并二叉树
题目连接：https://leetcode.cn/problems/merge-two-binary-trees/
思路一：使用前序遍历两个二叉树，遇到root1 == null return root2;遇到root2 == null return root1;
/**
* 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 mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
}
思路二：使用一个stack, 依次存放root2 root1, root1.val += root2.val,最后返回root1
/**
* 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 mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
Stack<TreeNode> stack = new Stack<>();
stack.push(root2);
stack.push(root1);
while (!stack.isEmpty()){
TreeNode treeNode1 = stack.pop();
TreeNode treeNode2 = stack.pop();
treeNode1.val += treeNode2.val;
if (treeNode1.right != null && treeNode2.right != null) {
stack.push(treeNode2.right);
stack.push(treeNode1.right);
} else {
if (treeNode1.right == null) {
treeNode1.right = treeNode2.right;
}
}
if (treeNode1.left != null && treeNode2.left != null) {
stack.push(treeNode2.left);
stack.push(treeNode1.left);
} else {
if (treeNode1.left == null) {
treeNode1.left = treeNode2.left;
}
}
}
return root1;
}
}
三、 700. 二叉搜索树中的搜索
题目连接：https://leetcode.cn/problems/search-in-a-binary-search-tree/
思路一：二叉搜索特性，左子树都比根节点小，右子数都比根节点大 使用递归法
/**
* 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 searchBST(root.right, val);
} else if (root.val > val) {
return searchBST(root.left, val);
} else {
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 searchBST(TreeNode root, int val) {
TreeNode cur = root;
while (cur != null) {
if (cur.val < val) {
cur = cur.right;
} else if (cur.val > val) {
cur = cur.left;
} else {
return cur;
}
}
return null;
}
}
四、 98. 验证二叉搜索树
题目连接：https://leetcode.cn/problems/validate-binary-search-tree/
思路一：使用中序 记录前一个节点，如果pre.val >= root.val 就返回false (使用递归中序方法)
/**
* 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 {
private TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
boolean isLeft = isValidBST(root.left);
if (!isLeft) return false;
if (pre != null && pre.val >= root.val) return false;
pre = root;
return isValidBST(root.right);
}
}
思路二：使用中序迭代法
/**
* 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) {
if (root == null) return true;
TreeNode cur = root;
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
TreeNode treeNode = stack.pop();
System.out.println(treeNode.val);
if (pre != null && pre.val >= treeNode.val) return false;
pre = treeNode;
cur = treeNode.right;
}
}
return true;
}
}
思路三：使用后序遍历
/**
* 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 {
private boolean isValidBST(TreeNode root, long min, long max) {
if (root == null) return true;
if (root.val <= min || root.val >= max) return false;
boolean isLeft = isValidBST(root.left, min, root.val);
if (!isLeft) return false;
return isValidBST(root.right, root.val, max);
}
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
}
网友评论