LeetCode刷题笔记——HOT100面试题（6）

算法
,

前序、中序、后序遍历

94. 二叉树的中序遍历

二叉树的中序遍历，可以有递归和非递归两种写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null || !stack.isEmpty()) {
            while (root!=null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

101. 对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root==null) return true;
        return isSymmetric(root.left, root.right);
    }

    public boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left==null && right==null) return true;
        if (left==null || right==null) return false;
        if (left.val!=right.val) return false;
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

104. 二叉树的最大深度

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

105. 从前序与中序遍历序列构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length==0 || inorder.length==0 || preorder.length!=inorder.length) return null;
        TreeNode root = buildTree(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder, int pl, int pr, int il, int ir) {
        if (pl>pr || il>ir) return null;
        TreeNode root = new TreeNode(preorder[pl]);
        int len = 0;
        while (inorder[il+len]!=preorder[pl]) len++;
        root.left = buildTree(preorder, inorder, pl+1, pl+len, il, il+len-1);
        root.right = buildTree(preorder, inorder, pl+1+len, pr, il+len+1, ir);
        return root;
    }
}

114. 二叉树展开为链表

二叉树展开为链表后，顺序与前序遍历相同。把左子树的展开替换到右子节点处即可得到链表。但如果直接用前序遍历，会导致丢失右子节点。因此采用后序遍历，从尾节点递归处理。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public TreeNode prev = null;
    public void flatten(TreeNode root) {
        if (root==null) return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
}

124. 二叉树中的最大路径和

对于一个节点，穿过该节点的最大路径和存在3种可能：

  • 该节点及其左、右子树；
  • 包含该节点的左子树，及其父节点；
  • 包含该节点的右子树，及其父节点。

其中第一种情况不需要计算其父节点值，直接与当前最大值比较；后两种情况需要传出路径和，节点路径和不大于0时，该路径需要舍去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {

    int res;

    public int maxPathSum(TreeNode root) {
        res = Integer.MIN_VALUE;
        pathSum(root);
        return res;
    }

    public int pathSum(TreeNode root) {
        if (root==null) return 0;
        int left = pathSum(root.left);
        int right = pathSum(root.right);
        int sum = root.val + left + right;
        res = Math.max(res, sum);
        sum = root.val + Math.max(left, right);
        return sum>0? sum: 0;
    }
}

226. 翻转二叉树

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

236. 二叉树的最近公共祖先

参见《剑指Offer》二叉树的最近公共祖先。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null || root==p || root==q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left==null) return right;
        if (right==null) return left;
        return root;
    }
}

543. 二叉树的直径

经过root节点的直径为其左右子树的高度和。深度优先搜索以每一个节点为根节点的子树，比较并保存最大直径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max;
    }

    public int depth(TreeNode root) {
        if (root==null) return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        max = Math.max(max, left+right);
        return Math.max(left, right)+1;
    }
}

617. 合并二叉树

1
2
3
4
5
6
7
8
9
10
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1==null) return t2;
        if (t2==null) return t1;
        TreeNode root = new TreeNode(t1.val+t2.val);
        root.left = mergeTrees(t1.left, t2.left);
        root.right = mergeTrees(t1.right, t2.right);
        return root;
    }
}

层次遍历

102. 二叉树的层次遍历

层次遍历通常会使用队列这一数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root==null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int count = queue.size();
            while (count>0) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                count--;
                if (node.left!=null) queue.offer(node.left);
                if (node.right!=null) queue.offer(node.right);
            }
            res.add(temp);
        }
        return res;
    }
}

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

方法一：DFS

按照先序遍历序列化和反序列化二叉树。

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
43
public class Codec {

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        if (root!=null) {
            serialize(root, sb);
            sb.deleteCharAt(sb.length()-1);
        }
        sb.append("]");
        return sb.toString();
    }

    public void serialize(TreeNode root, StringBuilder sb) {
        if (root==null) sb.append("null,");
        else {
            sb.append(root.val+",");
            serialize(root.left, sb);
            serialize(root.right, sb);
        }
    }

    public int index;

    public TreeNode deserialize(String data) {
        if (data.equals("[]")) return null;
        this.index = 0;
        String[] strs = data.substring(1, data.length()-1).split(",");
        return deserialize(strs);
    }

    public TreeNode deserialize(String[] strs) {
        String s = strs[index++];
        TreeNode node = null;
        if (s.equals("null")) return node;
        else {
            node = new TreeNode(Integer.parseInt(s));
            node.left = deserialize(strs);
            node.right = deserialize(strs);
        }
        return node;
    }
}

方法二：BFS

参考《剑指offer》序列化二叉树。

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
43
44
45
46
47
48
public class Codec {

    public String serialize(TreeNode root) {
        if (root==null) return "[]";
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node!=null) {
                sb.append(node.val+",");
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                sb.append("null,");
            }
        }
        sb.deleteCharAt(sb.length()-1);
        sb.append("]");
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.equals("[]")) return null;
        String[] nodes = data.substring(1, data.length()-1).split(",");
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        queue.offer(root);
        int i=1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (!nodes[i].equals("null")) {
                TreeNode left = new TreeNode(Integer.parseInt(nodes[i]));
                node.left = left;
                queue.offer(left);
            }
            i++;
            if (!nodes[i].equals("null")) {
                TreeNode right = new TreeNode(Integer.parseInt(nodes[i]));
                node.right = right;
                queue.offer(right);
            }
            i++;
        }
        return root;
    }
}

二叉搜索树相关

98. 验证二叉搜索树

二叉搜索树中左子树的所有节点值小于根节点的值，右子树的所有节点大于根节点的值，如果只递归比较根节点跟其左右子节点的值，会出现左子节点的右子节点值大于根节点值的情况，因此需要将根节点的值传递到下一层进行比较。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MAX_VALUE, Long.MIN_VALUE);
    }

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

538. 把二叉搜索树转换为累加树

反向中序遍历，更新节点值为累加和。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root==null) return root;
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }
}