package question0144_binary_tree_preorder_traversal;

import java.util.ArrayList;
import java.util.List;

/**
 * Morris前序遍历。
 *
 * 时间复杂度是O(n)，其中n为树中的节点个数。空间复杂度是O(1)。
 *
 * 执行用时：1ms，击败99.05%。消耗内存：35.3MB，击败40.72%。
 */
public class Solution4 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (null == root) {
            return list;
        }
        TreeNode cur = root;
        while (null != cur) {
            //前序遍历的访问顺序是先本节点，再左节点，再右节点
            if (null == cur.left) {
                //如果说当前节点的左孩子为null，就无需考虑其左子树，直接记录当前节点的值并访问右孩子即可
                list.add(cur.val);
                cur = cur.right;
            } else {
                //prev节点的含义是：当前节点在中序遍历时的前驱节点
                TreeNode prev = cur.left;
                while (null != prev.right && prev.right != cur) {
                    prev = prev.right;
                }
                //如果prev的右孩子为null，说明是第一次访问该节点
                if (null == prev.right) {
                    //令prev的右孩子为当前节点
                    prev.right = cur;
                    //记录该节点的值
                    list.add(cur.val);
                    //访问当前节点的左孩子
                    cur = cur.left;
                //如果prev的右孩子不为null，说明是第二次访问该节点
                } else {
                    //令prev的右孩子为null
                    prev.right = null;
                    //访问当前节点的右孩子
                    cur = cur.right;
                }
            }
        }
        return list;
    }
}