草稿圖網(wǎng)站
java的Deque
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;
}
}
總結(jié)
暫無
Leetcode 617.合并二叉樹
題目：617.合并二叉樹
解析：代碼隨想錄解析
解題思路
如果都為root1, root2都為空，返回null；如果root1為空，root2不為空，返回root2；如果roo1不為空，root2為空，返回root1，否則創(chuàng)建新節(jié)點(diǎn)，遞歸。
改進(jìn)：以root1為主樹，并對(duì)判斷條件減枝。
代碼
/**
* 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;
}
}
}
//改進(jìn),減少了一點(diǎn)點(diǎn)內(nèi)存消耗
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;
}
}
總結(jié)
暫無
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;
}
}
總結(jié)
暫無
Leetcode 98.驗(yàn)證二叉搜索樹
題目：98.驗(yàn)證二叉搜索樹
解析：代碼隨想錄解析
解題思路
中序遍歷，記錄上一個(gè)節(jié)點(diǎn)的值和現(xiàn)在的比，如果遍歷完就返回true。文章來源：http://www.zghlxwxcb.cn/news/detail-846290.html
代碼
/**
* 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;
}
}
總結(jié)
暫無文章來源地址http://www.zghlxwxcb.cn/news/detail-846290.html
到了這里，關(guān)于【算法刷題day20】Leetcode:654. 最大二叉樹、617.合并二叉樹、700. 二叉搜索樹中的搜索、98.驗(yàn)證二叉搜索樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
