Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Why DFS

I believe that the friends who have learned data structure know that DFS (depth-first search) is a very important search algorithm, may directly say that you feel not conditional you can go to see some algorithm competition. Every one of these games is going to involve DFS in some way or another, and DFS is probably something we all know about but we all know about it in order to avoid being too arrogant to write about it. In order to avoid this embarrassment we are going to take advantage of this activity for a few days to practice, well we don’t have to talk about fat.

PS: THESE days, I found that some fat friends do not know what DFS is. I’d better say it briefly, otherwise this problem will be difficult to do.

Depth First Search belongs to a graph algorithm, abbreviated as DFS, namely Depth First Search. The process is simply as deep as you can go into every possible branch path, and each node can only be accessed once.

For example, if we initiate A depth-first search from point A (the following access order is not unique, the second point could be either B or C or D), we might get an access process like A->B->E (no path! Backtrace to A)->C->F->H->G->D (no path, finally backtrace to A,A also has no adjacent node not visited, the search ends). The characteristic of depth-first search is briefly explained: the result of depth-first search must be a connected component of graph. Depth-first searches can be initiated from multiple points. If you sort each node by “end time” during a depth-first search (by creating a list, then adding that node to the end of the list if all of its neighbors have been accessed, and then reversing the entire list), Then we can get what is called “topological sort “, i.e. topological sort. [1]

The title

Give you the root node of a binary tree, root, and return a backward traversal of its node values.

Example 1:

Enter: root = [1.null.2.3] output: [3.2.1]
Copy the code

The sample2Input: root = [] Output: []Copy the code

The sample3: Enter: root = [1] output: [1]
Copy the code

First we need to understand what a binary tree is: the tree is traversed in the same way as the left subtree — the right subtree — the root node, and the left or right subtree is traversed in the same way until the entire tree is traversed. Therefore, the whole traversal process naturally has the nature of recursion, we can directly use recursive function to simulate this process.

Define postorder(root) to represent the answer currently traversed to the root node. By definition, we recursively call postorder(root->left) to traverse the left subtree of the root node, then recursively call postorder(root->right) to traverse the right subtree of the root node, and add the value of root to the answer. Recursion terminates when an empty node is encountered.

Solution: Top-down solution (slightly faster)

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    List list=new ArrayList();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root==null)return list;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        returnlist; }}Copy the code

Method 2:

We can also iterate on the recursive function of method 1. The difference is that the recursion maintains a stack implicitly, but we need to simulate the stack explicitly during iteration. The rest of the implementation and details are the same.

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while(root ! =null| |! stack.isEmpty()) {while(root ! =null) {// Find the leftmost leaf node of this node and push the left node along the way
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();// The node to be processed is out of the stack
            if (root.right == null || root.right == prev) {// Since this node is the leftmost leaf node, we only need to determine the right node prev is used to record the node to be pushed again
                res.add(root.val);
                prev = root;
                root = null;
            } else {// If there is a right node, then push to find the leftmost leaf node of that nodestack.push(root); root = root.right; }}returnres; }}Copy the code

conclusion

This iteration has a detailed answer, you can learn according to this article. Prevent interview questions.