leetcode - 02 树专题 226~662~98~297~剑指Offer36~958~剑指Offer54~111~104~222

226. 翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

662. 二叉树最大宽度

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if(root==null){
            return 0;
        }
        int res = 1;
        List<Pair<TreeNode,Integer>> arr = new ArrayList<>();
        arr.add(new Pair<TreeNode,Integer>(root, 1) );
        while (!arr.isEmpty()){
            res = Math.max(res,arr.get(arr.size()-1).getValue()-arr.get(0).getValue()+1);
            List<Pair<TreeNode,Integer>> list = new ArrayList<>();
            for (Pair<TreeNode, Integer> pair : arr) {
                TreeNode node = pair.getKey();
                Integer index = pair.getValue();
                if(node.left!=null){
                    list.add(new Pair<TreeNode,Integer>(node.left,2*index));
                }
                if(node.right!=null){
                    list.add(new Pair<TreeNode,Integer>(node.right,2*index+1));
                }
            }
            
            arr = list;
        }
        return res;
    }
}
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

class Solution {
    Map<Integer,Integer> levelMin = new HashMap<>();
    public int widthOfBinaryTree(TreeNode root) {
        int index = 1;
        int depth = 1;
        return dsf(root,depth,index);
    }

    private int dsf(TreeNode root, int depth, int index) {
        if(root==null) {
            return 0;
        }
        levelMin.putIfAbsent(depth,index);
        // 当前节点的宽度
        int width = index-levelMin.get(depth)+1;
        // 最左节点到当前节点的宽度
        int leftWidth = dsf(root.left,depth+1,2*index);
        int rightWidth = dsf(root.right,depth+1,2*index+1);
        return Math.max(width,Math.max(leftWidth,rightWidth));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

98. 验证二叉搜索树

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

    private boolean valid(TreeNode root, long minValue, long maxValue) {
        if(root==null){
            return true;
        }
        if(root.val<=minValue || root.val>=maxValue){
            return false;
        }
        // 递归左子节点和右子节点
        return valid(root.left,minValue,root.val) && valid(root.right,root.val,maxValue);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

中序遍历：

class Solution {
    List<Integer> res = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        // 二叉搜索树中序遍历的值一定是升序的
        if(root==null){
            return true;
        }
        inorder(root);
        for(int i=1;i<res.size();i++){
            if(res.get(i)<=res.get(i-1)){
                return false;
            }
        }
        return true;
    }

    private void inorder(TreeNode root) {
        if(root==null){
            return;
        }
        inorder(root.left);
        res.add(root.val);
        inorder(root.right);
    }
}
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

297. 二叉树的序列化与反序列化

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return reserialize(root,"");
    }

    private String reserialize(TreeNode root, String str) {
        if(root==null){
            str += "None,";
        }else {
            str += str.valueOf(root.val) +",";
            str = reserialize(root.left,str);
            str = reserialize(root.right,str);
        }
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] split = data.split(",");
        List<String> dataList = new LinkedList<>(Arrays.asList(split));
        return redeserialize(dataList);
    }

    private TreeNode redeserialize(List<String> dataList) {
        if(dataList.get(0).equals("None")){
            dataList.remove(0);
            return null;
        }
        Integer rootValue = Integer.valueOf(dataList.get(0));
        TreeNode root = new TreeNode(rootValue);
        dataList.remove(0);
        root.left = redeserialize(dataList);
        root.right = redeserialize(dataList);
        return root;
    }
}
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

剑指 Offer 36. 二叉搜索树与双向链表

https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/tu-wen-bing-mao-zui-tong-su-yi-dong-de-t-0adg/

class Solution {
    // 前驱节点
    Node pre = null;
    // 头节点
    Node head = null;
    public Node treeToDoublyList(Node root) {
        if(root==null){
            return root;
        }
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    private void dfs(Node root) {
        if(root==null) return;
        // 中序遍历
        // 处理左子节点
        dfs(root.left);
        // 处理当前节点
        if(pre==null){
            // 说明遍历的是头结点
            head = root;
            root.left = pre;
        }else{
            // 说明遍历到的不是头节点
            pre.right = root;
            root.left = pre;
        }
        pre = root;
        // 处理右子节点
        dfs(root.right);
    }
}
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

958. 二叉树的完全性检验

层序遍历：

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        boolean flag = true;
        Queue<TreeNode> queue =  new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left!=null){
                // 如果上一个节点为null，则说明不是完全二叉树
                if(!flag){
                    return false;
                }
                queue.add(node.left);
            }else{
                flag = false;
            }
            if(node.right!=null){
                // 如果上一个节点为null，则说明不是完全二叉树
                if(!flag){
                    return false;
                }
                queue.add(node.right);
            }else {
                flag = false;
            }
        }
        return true;
    }
}
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

深度搜索：

class Solution {
    int size = 0;
    int maxIndex = 0;
    public boolean isCompleteTree(TreeNode root) {
        if(root==null){
            return true;
        }
        // 给二叉树进行编号
        int rootIndex = 1;
        recurize(root,rootIndex);
        // 树的size是否等于最后一个节点的编号
        return maxIndex==size;
    }

    private void recurize(TreeNode root, int index) {
        if(root==null){
            return;
        }
        size++;
        if(size>=100){
            return;
        }
        maxIndex = Math.max(index,maxIndex);
        recurize(root.left,2*index);
        recurize(root.right,2*index+1);
    }
}
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

剑指 Offer 54. 二叉搜索树的第k大节点

class Solution {
    // 记录第k大节点的值
    int res;
    int k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        // 逆序中序遍历
        dfs(root);
        return res;
    }

    private void dfs(TreeNode root) {
        if(root==null){
            return;
        }
        // 遍历右子树
        dfs(root.right);
        // 遍历根节点
        if(k==0){
            return;
        }
        // 记录第k
        if(--k==0){
            res = root.val;
        }
        // 遍历左子树
        dfs(root.left);
    }
}
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

方法2：

class Solution {
    // 记录第k大节点的值
    List<Integer> list = new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        // 逆序中序遍历
        dfs(root);
        return list.get(k-1);
    }

    private void dfs(TreeNode root) {
        if(root==null){
            return;
        }
        dfs(root.left);
        list.add(0,root.val);
        dfs(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

111. 二叉树的最小深度

class Solution {
    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return dfs(root);
    }

    private int dfs(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftDepth = dfs(root.left);
        int rightDepth = dfs(root.right);

        // 这种情况一定要考虑，否则就不对了，当有一侧为null时，不能去取0
        if(root.left==null || root.right==null){
            return leftDepth+rightDepth+1;
        }
        return Math.min(leftDepth,rightDepth)+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

104. 二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth,rightDepth)+1;
    }
}
1
2
3
4
5
6
7
8
9
10

222. 完全二叉树的节点个数

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        return dfs(root);
    }

    private int dfs(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftCount = dfs(root.left);
        int rightCount = dfs(root.right);
        return leftCount+rightCount+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17