654.最大二叉树

文章:19. 最大二叉树

题目:654. 最大二叉树

视频:又是构造二叉树,又有很多坑!| LeetCode:654.最大二叉树_哔哩哔哩_bilibili

【思路】

构造二叉树类型的题目,我们都使用前序遍历对二叉树进行构造。

先构造中间节点,再构造左子树,最构造右子树

递归

1.确递归函数的参数和返回值

2.确定终止条件

  • 当传入的数组大小为1的时候,说明遍历到了叶子节点
  • 那么应该定义一个新节点,把这个数组的数值赋给新的节点,然后返回这个节点。

3.确定单层递归的逻辑

  • 先找到数组中最大值和对应的下标,最大的值构造根节点,下标用来下一步分割数组。
  • 最大值所在的下标左区间 构造左子树
  • 最大值所在的下标右区间 构造右子树
  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return traversal(nums,0,nums.length);
}
public TreeNode traversal(int[] nums,int s,int e){
if(s >= e)return null;
int maxIndex = s;
for(int i = s+1 ;i <e;i++){
if(nums[i] > nums[maxIndex]) maxIndex = i;
}
TreeNode n = new TreeNode(nums[maxIndex]);

n.left = traversal(nums,s,maxIndex);
n.right = traversal(nums,maxIndex+1,e);
return n;

}
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func constructMaximumBinaryTree(nums []int) *TreeNode {
return traversal(nums)
}
func traversal(nums []int)*TreeNode{
if len(nums) == 0 {
return nil
}
maxIndex := 0
for i,v := range nums{
if v > nums[maxIndex]{
maxIndex = i
}
}
node := &TreeNode{
Val:nums[maxIndex],
Left:traversal(nums[:maxIndex]),
Right:traversal(nums[maxIndex+1:]),
}
return node
}

617.合并二叉树

文章:21. 合并二叉树

题目:617. 合并二叉树

视频:一起操作两个二叉树?有点懵!| LeetCode:617.合并二叉树_哔哩哔哩_bilibili

【思路】

使用前序遍历。一开始通过root1root2是否为空作为判断条件,有效的解决了出现如果root1root2为空&&root1==null &&root2==null,然后通过递归来获取左子树和右子树。

  • Java实现
1
2
3
4
5
6
7
8
9
10
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;
}
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
if root1 == nil{
return root2
}
if root2 == nil{
return root1
}
root1.Val += root2.Val
root1.Left = mergeTrees(root1.Left,root2.Left)
root1.Right = mergeTrees(root1.Right,root2.Right)
return root1
}

700.二叉搜索树中的搜索

文章:22. 二叉搜索树中的搜索

题目:700. 二叉搜索树中的搜索

【思路】

二叉搜索树是一个有序树

  • 若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值
  • 若它的右子树不为空,则柚子树上所有系欸但的值均大于它的根节点的值
  • 它的左、右子树也分别为二叉搜索树

需要新建一个变量来承接递归后的值,而不是修改原来的root节点。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root == null || root.val == val)return root;
TreeNode result = new TreeNode();
if(root.val > val){
result = searchBST(root.left,val);
}
if(root.val < val){
result = searchBST(root.right,val);
}

return result;
}
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
func searchBST(root *TreeNode, val int) *TreeNode {
if root == nil || root.Val == val{
return root
}
result := &TreeNode{}
if root.Val > val{
result = searchBST(root.Left,val)
}
if root.Val < val {
result = searchBST(root.Right,val)
}
return result
}

23.验证二叉搜索树

文章:23. 验证二叉搜索树

题目:98. 验证二叉搜索树

视频:你对二叉搜索树了解的还不够! | LeetCode:98.验证二叉搜索树_哔哩哔哩_bilibili

【思路】

误区:只判断了 if root.Left.Val >= root.Val || root.Right.Val < root.Val,而忽略了二叉搜索树的根节点也大于左子树的全部节点,小于右子树的全部节点。

  • Java实现(不是很理解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    TreeNode max;
    public boolean isValidBST(TreeNode root) {
    if(root ==null)return true;
    boolean left= isValidBST(root.left);
    if(!left)return false;
    if(max!=null && root.val <= max.val){
    return false;
    }
    max = root;
    boolean right = isValidBST(root.right);
    return right;
    }
    }
  • Go实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func isValidBST(root *TreeNode) bool {

if root ==nil {
return true
}
return check(root,math.MinInt64,math.MaxInt64)
}
func check(node *TreeNode ,min ,max int64)bool {
if node == nil{
return true
}
if min >= int64(node.Val)||max <= int64(node.Val){
return false
}
return check(node.Right,int64(node.Val),max)&&check(node.Left,min,int64(node.Val))
}

【算法总结】

  • 最大二叉树:构造二叉树类型的题目,我们都使用前序遍历对二叉树进行构造。

  • 合并二叉树:递归实现

  • 二叉搜索树中的搜索:递归实现,需要新建一个变量来承接递归后的值,而不是修改原来的root节点。

  • 验证二叉搜索树:

    • 误区:只判断了 if root.Left.Val >= root.Val || root.Right.Val < root.Val,而忽略了二叉搜索树的
    • 但是不是很理解java的解法是什么意思,希望后面复盘的时候可以再看一遍!