LeetCode：654.最大二叉树

1.思路

解决方案：

• 单调栈是本题的最优解，这里将单调栈题解本题的一个小视频放在这里
  单调栈求解最大二叉树的过程
• 当然这里还有leetcode大佬给的解释，大家可以参考一下：
  思路很清晰，写得很棒
  

三句话描述单调栈的思路：

1. 当栈顶元素小于当前元素时，不断弹出栈顶元素，并把当前元素的左子赋值为栈顶元素;
2. 如果栈顶还有元素(那么一定比当前元素大)，就把顶元素的右子赋值为当前元素;
3. 当前元素入栈;

• . 注意，这里的“左子赋值”指的是：将该节点以左节点的身份赋值给某某节点（如栈顶节点）
• . 注意，这里的“右子赋值”指的是：将该节点以右节点的身份赋值给某某节点（如数组的当前元素）
• . “当前元素”指的是，数组遍历的元素nums[i]

2.代码实现

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int n = nums.length;
        List<Integer> stack = new ArrayList<Integer>();
        TreeNode[] tree = new TreeNode[n];
        for (int i = 0; i < n; ++i) {
            tree[i] = new TreeNode(nums[i]);
            while (!stack.isEmpty() && nums[i] > nums[stack.get(stack.size() - 1)]) {
                tree[i].left = tree[stack.get(stack.size() - 1)];
                stack.remove(stack.size() - 1);
            }
            if (!stack.isEmpty()) {
                tree[stack.get(stack.size() - 1)].right = tree[i];
            }
            stack.add(i);
        }
        return tree[stack.get(0)];
    }
}

3.复杂度分析

3.举例分析，这里参考爪哇缪斯

LeetCode：617.合并二叉树

解决方案：

1.思路：

• 可以使用递归深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。

• 两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。

• 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；

• 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；

• 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。

2.代码实现

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }
}

3.复杂度分析

LeetCode：700.二叉搜索树中的搜索

解决方案：

1.思路：

2.代码实现

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (val == root.val) {
            return root;
        }
        return searchBST(val < root.val ? root.left : root.right, val);
    }
}

3.复杂度分析

4.疑惑思考

为什么递归实现，c++和java的逻辑不一样

• C++实现：

public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) return root;
        if (root->val > val) return searchBST(root->left, val);
        if (root->val < val) return searchBST(root->right, val);
        return NULL;      //为什么一定要加这句，前面分情况讨论时不是已经有return了吗？
    }
};

• java实现

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (val == root.val) {
            return root;
        }
        return searchBST(val < root.val ? root.left : root.right, val);
    }
}

LeetCode：98.验证二叉搜索树

问题描述

解决方案：

1.思路：

• 如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
• 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 它的左右子树也为二叉搜索树。
• 以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r)(l,r)(l,r) 的范围内（注意是开区间）。
• 如果 root 节点的值 val 不在 (l,r)(l,r)(l,r) 的范围内说明不满足条件直接返回，
• 否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。

2.代码实现

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
}

3.复杂度分析