前序遍历

package algorithm.树常见题.深度优先遍历;

import com.sun.source.tree.Tree;
import dataStructure.树.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * [144. 二叉树的前序遍历](https://leetcode.cn/problems/binary-tree-preorder-traversal/description/)
 *
 */
public class preorderTraversal {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null) return ans;
        preTraversal(root, ans);
        return ans;
    }

    // 隐式递归结束条件
    private void preTraversal(TreeNode root, List<Integer> res) {
        res.add(root.val);
        if (root.left != null) preTraversal(root.left, res);
        if (root.right != null) preTraversal(root.right, res);
    }


    // 递归：显式递归结束条件
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }

    private void preorder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }

    // 解法二：迭代
    // 前序遍历顺序是[根，左，右]

    // 这个迭代的步骤是：
    //     大循环：判断栈和节点是否为空，只要有一个不空，就继续处理
    //         小循环：当前节点不为空
    //               1.把当前节点的值塞到结果数组里（因为根左右，当前节点就是对于其子节点来说，就是根，直接塞）
    //               2.把当前节点压栈（因为当前节点的值处理，当前节点可能还有【右】节点没有处理）
    //               3.当前节点=当前节点的左子节点
    //         小循环结束后，意味着树左侧节点处理完毕，从栈中弹节点，处理未处理的【右】子节点
    //               当前节点的 = 当前节点的右子节点
    public List<Integer> preorderTraversal3(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;  // 这里为什么要多个变量？
        while (!stack.isEmpty() || node != null) {
            while (node != null) { // 不停的将左子树压栈，并且根值塞到结果数组里
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            // 代码运行到这里，左侧子树已经在结果数组里了
            // 弹栈处理每个节点的右子节点
            node = stack.pop();
            node = node.right;
        }
        return res;
    }

    // 解法三：Morris遍历（最优）
    // TODO 暂时理解不了，后面再来看吧
    public static List<Integer> preorderTraversal4(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        TreeNode p1 = root, p2 = null;
        while (p1 != null) {
            p2 = p1.left;
            if (p2 != null) {
                while (p2.right != null && p2.right != p1) {
                    p2 = p2.right;
                }
                if (p2.right == null) {
                    res.add(p1.val);
                    p2.right = p1;
                    p1 = p1.left;
                    continue;
                } else {
                    p2.right = null;
                }
            } else {
                res.add(p1.val);
            }
            p1 = p1.right;
        }
        return res;
    }

    public static void main(String[] args) {
        // 跑一下Morris遍历，看代码看不懂
        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        List<Integer> ret = preorderTraversal4(root);
        System.out.println(ret.toString());
    }
}

中序遍历

package algorithm.树常见题.深度优先遍历;

import dataStructure.树.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * [94. 二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal/description/)
 *
 */
public class inorderTraversal {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    // 解法一：递归方式
    private void inorder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }

    // 解法二：迭代
    // 中序遍历顺序是[左，根，右]


    // 这个迭代的步骤是：
    //   大循环：判断栈和节点是否为空，只要有一个不空，就继续处理
    //           小循环：当前节点不为空
    //                 1. 栈中塞入当前节点（因为顺序是左根右，所以要一直找到最左的节点，要把当前节点存起来）
    //                 2. 当前节点 = 当前节点.left
    //           小循环结束后，栈顶元素就是最左一个元素
    //           所以弹栈弹出来，值塞到结果数组中
    //           为什么要 root = root.right?
    //           （对于栈顶最左一个元素来说，是叶子节点，即是左，也是根了，值塞好就处理完了，左根处理完了，自然要处理右节点）
    //           （对于弹栈后的其他元素来说，自己本身作为根，刚值已经塞好了。前置的弹栈处理其左子，左值也塞好了，所以应该处理右节点）
    //
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

    // 解法三：Morris中序遍历
    // TODO 暂时理解不了，后面再来看吧
    public List<Integer> inorderTraversal3(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode predecessor = null;

        while (root != null) {
            if (root.left != null) {
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    predecessor.right = root;
                    root = root.left;
                }
                else {
                    res.add(root.val);
                    predecessor.right = null;
                    root = root.right;
                }
            }
            else {
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
}

后序遍历

package algorithm.树常见题.深度优先遍历;

import dataStructure.树.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * [145. 二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/description/)
 *
 */
public class postorderTraversal {

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    // 解法一：递归
    private void postorder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }

    // 解法二：迭代法
    // 后序遍历顺序是[左，右，根]


    // 这个迭代的步骤是：
    //   大循环：判断栈和节点是否为空，只要有一个不空，就继续处理
    //           小循环：当前节点不为空
    //                 1. 栈中塞入当前节点（因为顺序是左右根，所以要一直找到最左的节点，要把当前节点存起来）
    //                 2. 当前节点 = 当前节点.left
    //           小循环结束后，栈顶元素就是最左一个元素
    //           if else 什么意思？
    //           （当前弹出的节点是最左节点，节点right是null的，把左节点塞到结果里）
    //            // TODO 这里有点儿难理解了
    public static List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        List<Integer> res = postorderTraversal2(tree);
        System.out.println(res.toString());
    }
}