Flog

阿酱日常写码的碎碎念

0%

Data Structure with examples

Posted on Edited on In
Symbols count in article: 9.6k Reading time ≈ 9 mins.

Data Structure with examples

  • ⌨️ Example code was written in Java and most of them are from LeetCode
  • 🧑🏻‍💻 Hope this note could help someone

Tree

树的遍历

前中后序遍历-介绍

树🌲是一种数据结构，用来模拟具有树状结构性质的数据合集。树的每一个节点都有一个值和一个包含所有子节点的列表,树也可以视为一个拥有N个节点和N-1条边的有向无环图。

二叉树是一种更为典型的树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

前、中、后序遍历都是DFS(深度优先搜索)。

树有4⃣️种遍历方法：

  • 前序遍历特点： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序
  • 中序遍历特点： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序
  • 后序遍历特点： 节点按照 [ 左子树 | 右子树 | 跟节点 ] 排序
  • 层序遍历

树的遍历框架：

  • 先序遍历
    • 判空
    • 访问节点
    • 左孩子入栈（再次从 1 开始执行）
    • 右孩子入栈（再次从 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
30
class Solution_144_0{
    //递归解法
    ArrayList<Integer> res = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root!=null){
            res.add(root.val);
            if (root.left!=null) preorderTraversal(root.left); //前序遍历：根左右
            if (root.right!=null) preorderTraversal(root.right);
        }
        return res;
    }
}

class Solution_144_1{
    //迭代解法
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root==null) return new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>(); // 用队列来保存节点，顺序是根左右
        ArrayList<Integer> res = new ArrayList<>(); // 保存节点值

        stack.push(root); // 添加根
        while (!stack.isEmpty()){
            TreeNode node = stack.pop(); //弹出栈顶元素
            res.add(node.val); // 添加值
            if (node.right!=null) stack.push(node.right); // 因为是前序遍历，所以添加完根之后去添加左子树
            if (node.left!=null) stack.push(node.left); // 因为是stack结构，所以右子树先add，放在栈下，左子树放在栈顶
        }
        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
28
29
30
31
32
33
class Solution_94_0{
  	// 中序遍历 递归做法
    ArrayList<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root!=null){
            if (root.left!=null) inorderTraversal(root.left); // 中序遍历：左根右 先将左子树全部遍历
            res.add(root.val);
            if (root.right!=null) inorderTraversal(root.right);
        }
        return res;
    }
}

class Solution_94_1{
    // 中序遍历 迭代做法
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root==null) return new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> res = new ArrayList<>();

        TreeNode cur = root; // 当前节点为root
        while (!stack.isEmpty() || cur!=null){
            while (cur!=null){
                stack.push(cur); // 如果当前节点不为null，则押入栈中
                cur = cur.left; // 并且更新cur节点为当前节点的左子节点
            }
            cur = stack.pop(); // 到达树的最左叶子时，弹出叶子，res添加当前节点的值
            res.add(cur.val);
            cur = cur.right; // 检查当前节点是否有右节点，如果没有则下次循环弹出当前节点的父节点
        }
        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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution_145_0{
  	// 后序遍历 递归做法
    ArrayList<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root!=null){
            if (root.left!=null) inorderTraversal(root.left);
            if (root.right!=null) inorderTraversal(root.right);
            res.add(root.val);
        }
        return res;
    }
}

class Solution_145_1{
    // 后序遍历 迭代做法
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode last = null;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode temp = stack.peek();
                //是否变到右子树
                if (temp.right != null && temp.right != last) {
                    cur = temp.right;
                } else {
                    list.add(temp.val);
                    last = temp;
                    stack.pop();
                }
            }
        }
        return list;
    }
}

class Solution_145_2{
    // 后序遍历 抖机灵做法
    // 利用LinkedList的addFirts方法，每次添加到在队首添加，最后顺序是：左右根
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root==null) return new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        LinkedList<Integer> res = new LinkedList<>()<>();

        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.addFirst(node.val); // 每次添加到队首，所以根被排到最后
            if (root.left!=null) stack.push(node.left); // 左节点押入栈底
            if (root.right!=null) stack.push(node.right); // 右节点先弹出
        }
        return res;
    }
}

层序遍历-介绍

层序遍历就是逐层遍历树结构。

层序遍历是BFS(广度优先搜索)，广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。

当我们在树中进行BFS时，我们访问的节点顺序就是逐层顺序遍历的。

层序遍历

层序遍历是BFS，利用queue来解决，每层里的元素用for loop来添加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<List<Integer>> levelOrder(TreeNode root) {
        /*
        整体思路和上一题差不多，不同点在于把每一层的node.val都集中在一个List中
        用for loop来把同一层的node全添加到list中并且把每次循环中
        当前的node的left和right child node全添加到queue中
        结束for loop后用res添加list
         */
        if (root==null) return new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<List<Integer>> res = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            for (int i=queue.size(); i>0;i--){
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left!=null) queue.add(node.left);
                if (node.right!=null) queue.add(node.right);
            }
            res.add(list);
        }
        return res;
}

递归解决树的问题

二叉树的最大深度

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

对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution_28_0{
    public boolean isSymmetric(TreeNode root) {
        //如果root根节点为null 直接返回true
        if(root==null) return true;
        return recur(root.left,root.right);
    }

    boolean recur(TreeNode left, TreeNode right){
        //如果左右节点都为null则是对称二叉树
        if(left==null && right==null) return true;
        //如果左右节点中有一个不为null而另一个为null则返回false,或者左右节点的值不同也返回false
        if(left==null || right==null || right.val!= left.val) return false;
        //递归左节点的左右子节点和右节点的左右自节点 用&&连接 来判断是否是对称二叉树
        return recur(left.left, right.right) && recur(left.right, right.left);
    }
}

路径总和

1
2
3
4
5
6
public boolean hasPathSum(TreeNode root, int sum) {
		if(root==null) return false;
		if(root.left==null && root.right==null) return sum==root.val;
		sum-=root.val;
		return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
}

常见题型+总结

从中序与后序遍历序列构造二叉树

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_106_0{
    /*
    跟07题类似
    还是要根据给出的中序遍历和后序遍历的结构找出root划分左右子树
    解题思路：postorder最后一个元素是root，root前面的元素是
    右子树的root，利用postorder中的root将inorder划分为左右
    子树，然后左右子树向下递归
    */
    HashMap<Integer,Integer> map = new HashMap<>(); //记录inorder，键值对是 inorder元素：元素 index
    int[] post; //备份postorder
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        post = postorder;
        for(int i=0;i<inorder.length;i++)
            map.put(inorder[i],i);
        return recur(postorder.length-1,0,inorder.length-1);// postRoot在postorder的最后一位
    }

    TreeNode recur(int postRoot,int inLeft,int inRight){
        if(inLeft>inRight) return null;// 到叶子节点返回null
        TreeNode root = new TreeNode(post[postRoot]);
        int inRoot = map.get(post[postRoot]);//找出inorder中的root的index
        //inRight-inRoot是右子树长度
        root.left = recur(postRoot-(inRight-inRoot)-1,inLeft,inRoot-1);
        root.right = recur(postRoot-1,inRoot+1,inRight);
        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
class Solution_07_0{
    // 解题的原理是：pre order遍历的第一个元素是root 利用这个root到in order遍历分为左子树和右子树，然后左右子树向下递归
    HashMap<Integer, Integer> map = new HashMap<>(); //记录in order遍历
    int[] preorder; // 记录pre order 的数组，递归方法中需要用到

    /**
     * @param preorder 前序遍历数组
     * @param inorder 中序遍历数组
     * @return TreeNode数组
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder; //存入preOrder
        for (int i=0; i<inorder.length;i++)
            // inOrdre元素:index
            map.put(inorder[i],i); //记录中序遍历中每一个元素的index
        return recur(0,0,inorder.length-1); //preRootIndex为0是因为要从preorder的第一个也就是整个树的root开始
    }

    /**
     * @param preRoot 前序遍历中root的索引(index)
     * @param inLeft 中序遍历的左边界
     * @param inRight 中序边界汇总的右边界
     */
    TreeNode recur(int preRoot, int inLeft, int inRight){
        if (inLeft > inRight) return null; //如果左边界大于右边界说明inOrder数组中越界了 直接返回null
        TreeNode root = new TreeNode(preorder[preRoot]); //new一个root的TreeNode对象
        int inRoot = map.get(preorder[preRoot]); //通过前序遍历的index来得到中序遍历中当前元素的index
        //因为已经知道该元素在中序遍历中的index，我们就可以区分出左右子树
        root.left = recur(preRoot+1,inLeft,inRoot-1); //左子树
        // 右子树root在前序遍历中的index = 当前root在前序遍历的index + (当前root在中序遍历中的index-中序遍历左边界)(这个是左子树的长度) +1(再加一)
        root.right = recur(preRoot+(inRoot-inLeft)+1,inRoot+1,inRight); //右子树
        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
class Solution_116_0{
    // 该解法也可以解答117题
    /*
    这道题就是给一个完美二叉树，从上到下遍历每一层，然后按层修改每一个节点的next
    比如：第二层的第一个节点的next指向第二个节点，第二个指向null
    对于每一个层就是一个单层链表
    需要注意的是：完美二叉树就是满二叉树，每一个节点只要有左节点就一定有右节点

    解法：层序遍历安BFS+队列
    步骤：
    1、添加root到队列，然后遍历每一层节点
    2、取出并删除队首节点
    3、如果当前节点不是该层最右边节点，就将取出的节点的next指向当前队列的队首
    4、如果当前节点有左右子树则加入队列
     */
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<>();
        if (root==null) return null;
        queue.add(root);
        while (!queue.isEmpty()){
            for (int i=queue.size();i>0;i--){
                Node node = queue.poll(); // 得到队首元素并在队列中删除该元素
                if (i>1) node.next = queue.peek(); // 得到上一行的元素后面一位元素
                if (node.left!=null) queue.add(node.left);
                if (node.right!=null) queue.add(node.right);
            }
        }
        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
class Solution_236_0{
    /*
    解题思路：
    要想找到两个节点的最近公共祖先节点，我们可以从两个节点往上找，每个节点都往上走，
    一直走到根节点，那么根节点到这两个节点的连线肯定有相交的地方，如果是从上往下走，
    那么最后一次相交的节点就是他们的最近公共祖先节点。
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode,TreeNode> parent = new HashMap<>(); // 记录每一个节点的父节点，键值对：子节点：父节点
        Queue<TreeNode> queue = new LinkedList<>(); // BFS需要用队列

        parent.put(root,null);// root没有父节点
        queue.add(root); // 从根节点一层一层往下找
        while (!parent.containsKey(p) || !parent.containsKey(q)){// 知道两个节点都被找到
            TreeNode node = queue.poll(); //队首元素出队
            if (node.left!= null){
                parent.put(node.left, node); //左节点不为空则记录下他的父节点
                queue.add(node.left);
            }
            if (node.right!= null){
                parent.put(node.right, node);
                queue.add(node.right);
            }
        }

        Set<TreeNode> ancestors = new HashSet<>(); //不同节点可以有同一个父节点，所以用set来记录
        while (p!=null){
            ancestors.add(p); //从p节点往上遍历，一直到root
            p = parent.get(p); // 更新p为当前p的父节点
        }
        while (!ancestors.contains(q)){
            // 查看p和p的祖先节点是否包含q，如果包含q则直接返回q，
            // 如果不包含则再次查看是否包含q的父节点，并返回q的父节点
            q = parent.get(q);
        }
        return q;
    }
}