【算法刷题day20】Leetcode:654. 最大二叉树、617.合并二叉树、700. 二叉搜索树中的搜索、98.验证二叉搜索树

文章目录

• • Leetcode 654. 最大二叉树
  • • 解题思路
    • 代码
    • 总结
    • Leetcode 617.合并二叉树
    • • 解题思路
      • 代码
      • 总结
      • Leetcode 700. 二叉搜索树中的搜索
      • • 解题思路
        • 代码
        • 总结
        • Leetcode 98.验证二叉搜索树
        • • 解题思路
          • 代码
          • 总结

            草稿图index.php/tags-333.html" class="superseo">网站

            
            （）

            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  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.合并二叉树

            题目：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 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 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.left, val);
                    return null;
                }
            }
            //不递归直接搜
            class Solution {
                public TreeNode searchBST(TreeNode root, int val) {
                    while (root != null) {
                        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 
                public boolean isValidBST(TreeNode root) {
                    if (root == null)
                        return true;
                    Stack
                        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;
                }
            }
            

            总结

            暂无