题目
给你二叉树的根节点 root ，返回它节点值的 前序 **遍历。
输入： root = [1,null,2,3] 输出： [1,2,3]
题解
第一种
我们先初始化数组 res 为空，将当前节点 root 设为根节点。如果左子树 exist，则在左子树中，找到当前节点 root 的 inorder遍历的前驱节点 t。t是左子树中最右边的节点，它满足t.right == null 或 t.right == root。如果 t.right == null，则将root加入res数组，然后将 t.right 设为 root，将 root 更新为root.left。此时，我们可以认为 t.right 是 root 的后继节点。如果 t.right == root，则说明当前节点的左子树已经遍历完成，将 t.right 设为 null，将 root 更新为 root.right。此时，我们已经遍历完成 root 的左子树和根节点。重复上述步骤，如果左子树不存在，则将 root 的值加入 res 数组，然后将 root 更新为 root.right。此时，我们已经遍历完成root的左、右子树和根节点。重复步骤1。如果 root 为 null，则说明遍历完成，返回 res 数组。
var preorderTraversal = function(root) { const res = []; while(root) { if(root.left) { let t = root.left; while(t.right && t.right != root) { t = t.right; } if(!t.right) { res.push(root.val); t.right = root; root = root.left; } else { t.right = null; root = root.right; } } else { res.push(root.val); root = root.right; } } return res; };
第二种
首先定义了一个空数组 res，用来存放遍历后的结果。如果输入的节点为空，则直接返回结果数组。接下来，定义了一个栈 stack，将根节点压入栈中。然后进行循环操作，从栈中弹出一个节点，并将该节点的值压入结果数组 res 中。如果该节点的右子节点不为空，则将其右子节点压入栈中。如果该节点的左子节点不为空，则将其左子节点压入栈中。循环直到栈为空，最后返回结果数组 res
var preorderTraversal = function(root) { const res = []; if(root === null) return res; const stack = []; stack.push(root); while(stack.length > 0){ const cur = stack.pop(); res.push(cur.val); if(cur.right !== null) stack.push(cur.right); if(cur.left !== null) stack.push(cur.left); } return res; };
