1. Three kinds of sequential traversal

Binary tree traversal, node variables will be saved in the stack frame, until the completion of the whole function, the node will be removed from the stack frame. You can also use Pre to save the values of previous nodes.

private List<Integer> results = new ArrayList<>();
Copy the code

** Sequential traversal: ** root node, left subtree, right subtree.

public void travesal(TreeNode root) {
    if (root == null) return;
    results.add(root.val);
    travesal(root.left);
    travesal(root.right);
}
Copy the code

** Order traversal: ** left subtree, root node, right subtree.

public void travesal(TreeNode root) {
    if (root == null) return;
    travesal(root.left);
    results.add(root.val);
    travesal(root.right);
}
Copy the code

**** sequential traversal: **** Left subtree, right subtree, root node.

public void travesal(TreeNode root) {
    if (root == null) return;
    travesal(root.left);
    travesal(root.right);
    results.add(root.val);
Copy the code

2. Four middle-order traversal methods

Morris: 🐂🐂🐂

The space complexity is constant, and there are many steps to execute.

public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); // First assign the root node to cur TreeNode cur = root; // Continue traversing while (cur! = null) {if (cur.left == null) {// If (cur.left == null) {// If (cur.left == null) {// If (cur.left == null) {// If (cur.left == null) {// If (cur.left == null) {// If (cur.left == null) {// If (cur.left == null) {// cur = cur.right; } else { TreeNode pre = cur.left; While (pre. Right!) = cur (pre. Right! = null && pre.right ! = cur) pre = pre.right; If (pre. Right == null) {pre. Right = cur; cur = cur.left; } else {// If the right pointer of the pre node is not null, it must point to a cur node. // If the left child of the pre node is traversed, we need the right pointer of the Pre node to point to null to restore the tree. Finally, the current node cur points to its right child node. pre.right = null; res.add(cur.val); cur = cur.right; }}Copy the code

Recursive method

The core of recursive methods is the stack. Each function has its own stack frame, even if the function itself calls will generate a stack frame. Each stack frame stores the variable and return address. When the binary tree traversal, the node variables will be stored in the stack frame, until the completion of the function, the node will be removed from the stack frame.

public void inOrderTraversal(TreeNode node) {
    if (node == null)
        return;
    inOrderTraversal(node.left);
    System.out.println(node.val);
    inOrderTraversal(node.right);
}
Copy the code

Recursive method stack frames are shown below.

Non-recursive methods

The core of the non-recursive call is still using the stack, which is to simulate the recursive stack frame. The called function stack frame holds the return address of the last called function, and we can know the execution status of each function, whether the left node is pushed, the right node is pushed, or the ejection of the stack.

public List<Integer> postorderTraversal(TreeNode root) { if (root == null) return Collections.emptyList(); Stack<TreeNode> stack = new Stack<TreeNode>(); List<Integer> results = new ArrayList<>(); stack.push(root); while(! stack.isEmpty()) { TreeNode top = stack.pop(); if (top ! = null) { if (top.right ! = null) stack.push(top.right); stack.push(top); stack.push(null); if (top.left ! = null) stack.push(top.left); } else { results.add(stack.pop().val); } } return results; }Copy the code