[LeetCode] 513.找树左下角的值（java实现、非递归法）
1. 题目
2. 读题（需要重点注意的东西）
使用二叉树的前序遍历模板，可以使用递归很简单的解决这个问题。但是你能否使用非递归的方法实现二叉树的前序遍历呢？
3. 解法
解法一：递归法
/**
* 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;
* }
* }
*/
class Solution {
List<Integer> list = new ArrayList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) return list;
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}
}
解法二：非递归法
需要注意的是，二叉树的前序遍历是中左右，因此在入栈时，需要先入右孩子，再入左孩子，这样输出出来的结果才是中左右。
/**
* 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;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null) return list;
// 将第一个根节点压入栈
stack.push(root);
// 用栈实现迭代
while(!stack.isEmpty()){
TreeNode node = stack.pop();
list.add(node.val);
if(node.right != null) stack.push(node.right);
if(node.left != null) stack.push(node.left);
}
return list;
}
}
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
6. 总结
要使用非递归的方式解决这道题，就需要理解前序遍历的思想以及实现过程，再结合这个过程使用合适的数据结构（如若需要先进先出，使用队列；若需要先进后出，使用栈，等等）进行操作。