文章目录
Leetcode 654. 最大二叉树
题目：654. 最大二叉树
解析：代码随想录解析
解题思路
NLR的建树
代码
/**
* 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 constructMaximumBinaryTree(int[] nums) {
return buildTree(nums, 0, nums.length);
}
private TreeNode buildTree(int[] nums, int left, int right) {
if (left == right)
return null;
if (left + 1 == right)
return new TreeNode(nums[left]);
int mid = left;
int midNum = nums[left];
for (int i = left + 1; i < right; i++) {
if (nums[i] > midNum){
midNum = nums[i];
mid = i;
}
}
TreeNode newNode = new TreeNode(midNum);
newNode.left = buildTree(nums, left, mid);
newNode.right = buildTree(nums, mid + 1, right);
return newNode;
}
}
总结
暂无
Leetcode 617.合并二叉树
解题思路
如果都为root1, root2都为空，返回null；如果root1为空，root2不为空，返回root2；如果roo1不为空，root2为空，返回root1，否则创建新节点，递归。
改进：以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 && root2 == null)
return null;
else if (root1 != null && root2 == null)
return root1;
else if (root1 == null && root2 != null)
return root2;
else {
TreeNode newNode = new TreeNode(root1.val + root2.val);
newNode.left = mergeTrees(root1.left, root2.left);
newNode.right = mergeTrees(root1.right, root2.right);
return newNode;
}
}
}
//改进,减少了一点点内存消耗
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
root1.val = root1.val + root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
}
//前序遍历
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 node1 = stack.pop();
TreeNode node2 = stack.pop();
node1.val += node2.val;
if (node1.right != null && node2.right != null){
stack.push(node2.right);
stack.push(node1.right);
} else {
if (node1.right == null)
node1.right = node2.right;
}
if (node1.left != null && node2.left != null) {
stack.push(node2.left);
stack.push(node1.left);
}else {
if (node1.left == null)
node1.left = node2.left;
}
}
return root1;
}
}
//层序遍历
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root1);
queue.add(root2);
while (!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
node1.val += node2.val;
if (node1.left != null && node2.left != null) {
queue.add(node1.left);
queue.add(node2.left);
}else {
if (node1.left == null)
node1.left = node2.left;
}
if (node1.right != null && node2.right != null){
queue.add(node1.right);
queue.add(node2.right);
} else {
if (node1.right == null)
node1.right = node2.right;
}
}
return root1;
}
}
总结
暂无
Leetcode 700. 二叉搜索树中的搜索
题目：700. 二叉搜索树中的搜索
解析：代码随想录解析
解题思路
代码
/**
* 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 || root.val == val)
return root;
if (root.val < val)
return searchBST(root.right, val);
if (root.val > val)
return searchBST(root.left, val);
return null;
}
}
//不递归直接搜
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while (root != null) {
if (val < root.val) root = root.left;
else if (val > root.val) root = root.right;
else return root;
}
return null;
}
}
总结
暂无
Leetcode 98.验证二叉搜索树
题目：98.验证二叉搜索树
解析：代码随想录解析
解题思路
中序遍历，记录上一个节点的值和现在的比，如果遍历完就返回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 int pre = Integer.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);
}
}
//迭代
class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null)
return true;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
TreeNode node = stack.pop();
if (pre != null && pre.val >= node.val)
return false;
pre = node;
node = node.right;
}
return true;
}
}
总结
暂无
