# LeetCode 144. Binary Tree Preorder Traversal题目分析代码

Given a binary tree, return the preorder traversal of its nodes' values. For example:Given binary tree {1,#,2,3} , 1 \ 2 / 3

return [1,2,3] . Note: Recursive solution is trivial, could you do it iteratively?

Subscribe to see which companies asked this question.

# 代码

## 方法一，非递归，运用一个栈即可

```/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Preorder in ArrayList which contains node values.
*/
public ArrayList<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
ArrayList<Integer> preorder = new ArrayList<Integer>();

if (root == null) {
return preorder;
}

stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}

return preorder;
}

}```

## 方法二： 递归遍历

```public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Traversal(root,res);
return res;
}

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

Paste_Image.png

## 方法三 ： 分治法

```public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;

List<Integer> left = preorderTraversal(root.left);
List<Integer> right = preorderTraversal(root.right);

return res;
}```

Paste_Image.png

381 篇文章35 人订阅

0 条评论

## 相关文章

1534

### LeetCode144.二叉树的前序遍历&94.二叉树的中序遍历&145.二叉树的后序遍历

后序遍历的非递归代码得说一下，首先后序遍历得顺序是左右中，我们知道先序遍历的压栈顺序是先压右再压左，这样出来的顺序就是中左右，如果把先序遍历的压栈顺序稍微变一...

5743

2310

2333

### 基础算法

0.创建类 BinaryTreeNode 1.创建方法：传入根结点 2.判断根节点是否为空 3.判断左右结点是否同时为空 4.用self调用此方法，将根节点的左...

741

2701

2202

### 111.Minimum Depth of Binary Tree(Tree-Easy)

Given a binary tree, find its minimum depth. The minimum depth is the number of ...

2179

### Q100 Same Tree

Given two binary trees, write a function to check if they are the same or not. T...

3276

2195