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].

分析:

两种种方法:

  1. 递归法

    递归是最简单的。

  2. 迭代法

    迭代法使用一个栈来保存每个节点的右节点。列表 result 用来保存最后的结果。每次将节点值放入 relust 列表中,并将其右节点入栈,然后令该节点等于它的左节点,如果左节点为空,就令该节点等于栈顶元素,并让栈顶元素出栈。当节点为 null 时结束。

代码:

递归法:

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if(root != null) {
result.add(root.val);
result.addAll(preorderTraversal(root.left));
result.addAll(preorderTraversal(root.right));
}
return result;
}
}

迭代法:

public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<Integer>();
Stack<TreeNode> rightNodes = new Stack<TreeNode>();
TreeNode n = root;
while (n != null) {
result.add(n.val);
if (n.right != null) {
rightNodes.push(n.right);
}
n = n.left;
if (n == null && !rightNodes.empty()) {
n = rightNodes.pop();
}
}
return result;
}
}

or

public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode n = root;
stack.push(n);
while (!stack.empty()) {
n = stack.pop();
result.add(n.val);
if (n.right != null) stack.push(n.right);
if (n.left != null) stack.push(n.left);
}
return result;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :