leetcode系列之-树(tree)题型总结_tree算法题leetcode

树模板

对于树的题尤其是二叉树的题其主要要做的事就是要进行搜索。在搜索过程中解决问题。常见的搜索就是先序遍历。其基本代码如下：

有时候，我们需要一些变量来保存递归过程所需要的结果。
解决树的问题，最重要的就是搜索（不一定是常见的先序，中序，后序 搜索），我们需要在搜索中将问题进行求解。

递归求二叉树的高度

题目描述

算法思想： 一个节点的高度=max(左孩子的高度,右孩子的高度)+1。 进行先序遍历搜索，每次递归返回的时候统计其左右孩子中最大的深度。

代码实现

public int maxDepth(TreeNode root) {
        if(root.left==null&& root.right==null){
            return 1;
        }
        int left_depth=maxDepth(root.left);
        int right_depth=maxDepth(root.right);
        //+1 是为了带上自己
        return Math.max(left_depth,right_depth)+1;
    }
1
2
3
4
5
6
7
8
9

结果

路径总和112

题目简介

解题思路：现在大部分树的题大多使用递归解决。对于该道题用一个变量记录递归到某一层时，root到其根叶子节点的路径和。递归结束意味着要返回上一层，要减去该层的值进行复原。类似于二叉树的先序遍历。

public int count=0;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }

        count+=root.val;
        if(root.left==null && root.right==null){
            if(count==targetSum){
                return true;
            }
        }
        boolean left=hasPathSum(root.left,targetSum);
        boolean right=hasPathSum(root.right,targetSum);
        count-=root.val;
        return left||right;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解决

二叉树的镜像

题目描述：

算法思想：利用递归思想从下向上交换，然后一层一层得往上走。
代码实现

 public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot==null)
            return null;
        TreeNode treeNode = new TreeNode(pRoot.val);
            treeNode.right=Mirror(pRoot.left);
            treeNode.left=Mirror(pRoot.right);
            pRoot=treeNode;
            return pRoot;
    }
1
2
3
4
5
6
7
8
9

从上到下打印二叉树（“顺序遍历”）

解题思路： 因为这道题是从左到右顺序打印，不能使用常规搜索。我们需要一个队列，刚开始将root 节点加入到队列中。从队列中取元素，如果该元素的左右孩子不为空，将其加入到队列中。不断重复此过程，直到队列为空。这其实也是对二叉树的一种遍历，我愿称为“顺序遍历”。
代码实现

ArrayList<Integer> res=new ArrayList<>();
    Queue<TreeNode> queue=new LinkedList<>();
    public int [] PrintFromTopToBottom(TreeNode root) {
        if(root==null){
            //list 转为aarray
            int[] arr= res.stream()
                    .mapToInt(Integer::intValue)
                    .toArray();
            return arr;
        }

        queue.add(root);
        //类似先序遍历
        while(queue.size()>0){
            TreeNode treeNode=queue.peek();
            queue.remove();
            if(treeNode.left!=null){
                queue.add(treeNode.left);
            }
            if(treeNode.right!=null){
                queue.add(treeNode.right);
            }
            res.add(treeNode.val);
        }
        int[] arr= res.stream()
                .mapToInt(Integer::intValue)
                .toArray();
        return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

比较消耗时间的点在于类型的转化

树的子结构26

两个dfs ,第一个dfs 先先序遍历树A中的每一个节点n(A),第二个dfs ,判断是否具有相同的结构。用一个array数组进行存放每个节点判断的结果。
1

dfs2判断的终止条件。

• B==null return true , B的一个分支到头，返回true
• A==null return false， A为空，B不为空（上面的先判断），返回false
• A.val !=B.val return false

代码实现：

  public static void dfs(TreeNode A,TreeNode B,ArrayList<Boolean> list){
        // 找第一个节点

        if(A==null ){
            return ;
        }
        boolean flag=dfs2(A,B);
        list.add(flag);
        dfs(A.left,B,list);
        dfs(A.right,B,list);

    }
    //判断子结构
    public static Boolean dfs2(TreeNode A,TreeNode B){
        if(B==null){
            return true;
        }
        if(A==null){
            return false;
        }
        if(A.val!=B.val){
            return false;
        }
        Boolean left=dfs2(A.left,B.left);
        Boolean right=dfs2(A.right,B.right);
        return left && right;
    }

    public static  boolean isSubStructure(TreeNode A, TreeNode B) {
        if(B==null){
            return false;
        }
        ArrayList<Boolean> arrayList = new ArrayList<>();
        dfs(A,B,arrayList);
        int lens=arrayList.size();
        for(int i=0;i<lens;i++){
            if(arrayList.get(i)){
                return true;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

33 [二叉搜索树的后序遍历序列]

题目描述：

解题思路：
二叉搜索树条件： 左孩子< 根 < 右孩子
后序遍历 ： 左 右 根
所以数组最后一个元素 一定为根节点。找一个k ，k在数组中的位置中第一次大于根节点，说明其后面的数都为根节点的右孩子。进行判断，不满足则返回false。

代码实现

static boolean  dfs(int l,int r,int [] postorder){
        if(l>=r){
            return true;
        }
        int root=postorder[r];
        int k=l;
        // 找到一个孩子
        while(k<=r && postorder[k]<root ){
            k++;
        }
        
        for(int i=k;i<r;i++){
            if(postorder[i]<root){
                return false;
            }
        }

        return  dfs(l,k-1,postorder) && dfs(k,r-1,postorder);
    }

    public static  boolean verifyPostorder(int[] postorder) {
        int lens=postorder.length;
        if(lens<1){
            return false;
        }
        boolean flag=dfs(0,lens-1,postorder);
        return flag;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

未完待续