Unidirectional list inversion

1.1 train of thought

One-way list inversion actually changes the pointer field of each node from pointing to the next node to pointing to the previous node.

1. Three variables are required: preNode, curNode, and nextNode.
2. Iterate over a single linked list
   • Point nextNode curNode. Next
   • The pointer field of curNode points to the previous node
   • Point preNode curNode
   • Point curtNode nextNode

   Until you get to the last node.

3. Return preNode

1.2 code

public class Node {
    
    private Object data;/ / data domain
    private Node next;/ / pointer field
 
    public Node(Object data){
        this.data = data;
    }
 
    public Node(Object data,Node next){
        this.data = data;
        this.next = next;
    }
 
    public Object getData(a) {
        return data;
    }
 
    public void setData(Object data) {
        this.data = data;
    }
 
    public Node getNext(a) {
        return next;
    }
 
    public void setNext(Node next) {
        this.next = next; }}Copy the code

public static Node reverseListNode(Node head){
        // If the list is empty or has only one node, return the original list directly
        if (head == null || head.getNext() == null) {return head;
        }
        // The previous node pointer
        Node preNode = null;
        // The current node pointer
        Node curNode = head;
        // Next node pointer
        Node nextNode = null;
 
        while(curNode ! =null){
            nextNode = curNode.getNext();//nextNode points to the nextNode
            curNode.setNext(preNode);// Point the next field of the current node to the previous node
            preNode = curNode;// The preNode pointer moves backwards
            curNode = nextNode;// The curNode pointer moves backwards
        }
 
        return preNode;
    }
Copy the code

2 Binary tree traversal

There are four traversal methods commonly used by binary trees: pre-order traversal, middle-order traversal, post-order traversal and hierarchical traversal. Different traversal calculation methods have slightly different ideas. Let’s take a look at the main algorithm ideas of these four traversal methods:

1. Traverse the binary tree order first: root node – > left subtree – > right subtree, that is, visit the root node first, then the left subtree, and finally the right subtree. In the figure above, the preceding binary tree traversal result is: 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6

/** * 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 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(null == root){
            return result;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(! stack.isEmpty()){ TreeNode node = stack.pop(); result.add(node.val);if(node.right ! =null){
                stack.push(node.right);
            }
            if(node.left ! =null){ stack.push(node.left); }}returnresult; }}Copy the code

2, middle order traversal binary tree order: left subtree – > root node – > right subtree, that is, first visit the left subtree, then the root node, and finally the right subtree. The middle-order traversal result of binary tree in the figure above is: 3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(null == root){
            return result;
        }
        Stack stack = new Stack<TreeNode>();
        TreeNode curNode = root;
        while(curNode ! =null| |! stack.isEmpty()){while(curNode ! =null){
                stack.push(curNode);
                curNode = curNode.left;  
            }
            curNode = (TreeNode)stack.pop();
            result.add(curNode.val);
            curNode = curNode.right;
        }
        returnresult; }}Copy the code

3. Follow the order of traversing binary tree: left subtree – > right subtree – > root node, that is, visit the left subtree first, then the right subtree, and finally the root node. In the figure above, the backorder traversal result of binary tree is as follows: 3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        TreeNode curNode = root;
        TreeNode preNode = null; // Record the last node
        while(! stack.isEmpty() || curNode ! =null) {while(curNode ! =null){
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.peek();
            // After traversing the left and right subtrees, cur returns to the root. So whether you're currently going back to the root from the left subtree or the right subtree, you shouldn't do that anymore, you should go back up.
            // If you go back to the root from the right, you should go back to the top.
            // Add root = to the list if the subtree is right
            if(curNode.right == null || curNode.right == preNode){
                result.add(curNode.val);
                stack.pop();
                preNode = curNode;
                curNode = null;
            } else{ curNode = curNode.right; }}returnresult; }}Copy the code

4. Sequence traversal of binary tree: start from the topmost node, traverse from left to right, then turn to the second layer, continue to traverse from left to right, continue the cycle until all nodes have traversed the binary tree sequence traversal in the above figure: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6