給你二叉樹的根節(jié)點?root?疏魏，返回它節(jié)點值的前序?遍歷停做。
輸入：root = [1,null,2,3]輸出：[1,2,3]
輸入：root = []輸出：[]
輸入：root = [1]輸出：[1]
/**
?*?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;
?*?????}
?*?}
?*/
// 遞歸算法實現(xiàn)遍歷
class?Solution?{
????List<Integer>?treeList?=?new?ArrayList<Integer>();
????public?List<Integer>?preorderTraversal(TreeNode?root)?{
????????TreeNode?cur?=?root;
????????if?(cur?==?null)?{
????????????return?treeList;
????????}
????????treeList.add(cur.val);
????????if?(cur.left?!=?null)?{
????????????preorderTraversal(cur.left);
????????}
????????if?(cur.right?!=?null)?{
????????????preorderTraversal(cur.right);
????????}
????????return?treeList;
????}
}
代碼簡化如下：
class?Solution?{
????private?List<Integer>?preorder(TreeNode?node,?List<Integer>?list)?{
????????if?(node?==?null)?{
????????????return?list;
????????}
????????list.add(node.val);
????????preorder(node.left,?list);
????????preorder(node.right,?list);
????????return?list;
????}
????public?List<Integer>?preorderTraversal(TreeNode?root)?{
????????List<Integer>?list?=?new?ArrayList<Integer>();
????????return?preorder(root,?list);
????}
}
// 迭代方法
class?Solution?{
????public?List<Integer>?preorderTraversal(TreeNode?root)?{
????????List<Integer>?list?=?new?ArrayList<Integer>();
????????if?(root?==?null)?{
????????????return?list;
????????}
????????Deque<TreeNode>?stack?=?new?LinkedList<>();
????????TreeNode?node?=?root;
????????while?(!stack.isEmpty()?||?node?!=?null)?{
????????????while?(node?!=?null)?{
????????????????list.add(node.val);
????????????????stack.push(node);
????????????????node?=?node.left;
????????????}
????????????node?=?stack.pop();
????????????node?=?node.right;
????????}
????????return?list;
????}
}
