树相关leecode题目分类

遍历

  1. 树的深度优先遍历，前中后序（DFS）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void dfs(TreeNode root) {
    if (root == null) return;
    list.add(root.val);
    dfs(root.left);
    dfs(root.right);
}

private void dfs(TreeNode root) {
    if (root == null) return;
    dfs(root.left);
    list.add(root.val);
    dfs(root.right);
}

private void dfs(List<Integer> list, TreeNode root) {
    if (root == null) return;
    dfs(list, root.left);
    dfs(list, root.right);
    list.add(root.val);
}
  1. 树的广度遍历（BFS）
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
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (queue.size() > 0) {
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue1 = new LinkedList<>();
        while (queue.size() > 0) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                queue1.offer(node.left);
            }  
            if (node.right != null) {
                queue1.offer(node.right);
            }  
        }
        result.add(list);
        queue = queue1;
    }
    return result;
}
  1. 树的最大深度
1
2
3
4
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
  1. 判断树是否对称
1
2
3
4
5
6
7
8
9
10
public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isSame(root.left, root.right);
}

private boolean isSame(TreeNode root1, TreeNode root2) {
     if (root1 == null && root2 == null) return true;
     if (root1 == null || root2 == null) return false;
     return root1.val == root2.val && isSame(root1.left, root2.right) && isSame(root1.right, root2.left);
}
  1. 路径总和
1
2
3
4
5
6
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    int dx = sum - root.val;
    if (dx == 0 && root.left == null && root.right == null) return true;
    return hasPathSum(root.left, dx) || hasPathSum(root.right, dx);
}
  1. 树最近公共根节点
1
2
3
4
5
6
7
8
9
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (root == p || root == q) return root;
    TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
    TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
    if (leftNode != null && rightNode != null) return root;
    if (leftNode == null) return rightNode;
    return leftNode;
}
  1. 平衡二叉树
  2. 比较两棵树是否相同

重建

  1. 根据中序遍历和后序遍历，重建二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        List<Integer> inorderList = new ArrayList<>();
        for (int one : inorder) {
            inorderList.add(one);
        }
        List<Integer> postorderList = new ArrayList<>();
        for (int one : postorder) {
            postorderList.add(one);
        }
        return subBuildTree(inorderList, postorderList);
    }

    public TreeNode subBuildTree(List<Integer> inorder, List<Integer> postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return null;
        int val = postorder.get(postorder.size()-1);
        TreeNode root = new TreeNode(val);
        int index = inorder.indexOf(val);
        root.left = subBuildTree(inorder.subList(0, index), postorder.subList(0, index));
        root.right = subBuildTree(inorder.subList(index+1, inorder.size()), postorder.subList(index, postorder.size()-1));
        return root;
    }
}
  1. 根据前序遍历和中序遍历，重建二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) return null;
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i=0; i<inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return build(map, preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
}

private TreeNode build(HashMap<Integer, Integer> map, int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
    if (preLeft > preRight) return null;
    int val = preorder[preLeft];
    TreeNode node = new TreeNode(val);
    if (preLeft == preRight) return node; 

    int index = map.get(val);
    int leftSize = index - inLeft;
    int rightSize = inRight - index;
    node.left = build(map, preorder, preLeft+1, preLeft+leftSize, inorder, inLeft, inLeft+leftSize-1);
    node.right = build(map, preorder, preLeft+1+leftSize, preLeft+leftSize+rightSize, inorder, index+1, index+rightSize);
    return node;
}

修剪

  1. 同层连接所有节点
1
2
3
4
5
6
7
8
9
10
11
12
13
public Node connect(Node root) {
    if (root == null) return null;
    conn(root.left, root.right);
    return root;
}

private void conn(Node root1, Node root2) {
    if (root1 == null || root2 == null) return;
    root1.next = root2;
    conn(root1.left, root1.right);
    conn(root1.right, root2.left);
    conn(root2.left, root2.right);
}
  1. 连接同层所以节点，非完全二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public Node connect(Node root) {
    if (root == null) return null;

    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (queue.size() > 0) {
        Node pre = null;
        Queue<Node> tmp = new LinkedList<>();
        while (queue.size() > 0) {
            Node node = queue.poll();
            if (pre != null) pre.next = node;
            pre = node;
            if (node.left != null) tmp.offer(node.left);
            if (node.right != null) tmp.offer(node.right);
        }
        queue = tmp;
    }
    return root;
}

二叉搜索树

  1. 验证二叉搜索树
1
2
3
4
5
6
7
8
9
boolean valid = true;
TreeNode pre;
private void dfs(TreeNode root) {
    if (!valid) return;
    if (root == null) return;
    dfs(root.left);
    if (pre != null && pre.val >= root.val) valid = false;
    pre = root;
    dfs(root.right);
  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
28
29
class BSTIterator {

    Stack<TreeNode> stack = new Stack<>();
    public BSTIterator(TreeNode root) {
        if (root == null) return;
        stack.push(root);
        TreeNode p = root.left;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        TreeNode p = node.right;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        return node.val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.empty();
    }
}
  1. 搜索BST
1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode searchBST(TreeNode root, int val) {
    TreeNode p = root;
    while (p != null) {
        if (p.val > val) {
            p = p.left;
        } else if (p.val < val) {
            p = p.right;
        } else {
            return p;
        }
    }
    return null;
}
  1. BST插入节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    TreeNode p = root;
    while (p != null) {
        if (val > p.val) {
            if (p.right == null) {
                p.right = new TreeNode(val);
                break;
            }
            p = p.right;
        } else {
            if (p.left == null) {
                p.left = new TreeNode(val);
                break;
            }
            p = p.left;
        } 
    }
    return root;
}