描述
给出一棵二叉树,返回其中序遍历
样例
给出二叉树 {1,#,2,3},
1
\
2
/
3
返回 [1,3,2].
挑战
你能使用非递归算法来实现么?
中序
左根右
代码
/**
* 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: Inorder in ArrayList which contains node values.
*/
public ArrayList<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
ArrayList<Integer> result = new ArrayList<Integer>();
TreeNode curt = root;
// curt == null 但 stack 为非空 说明当前结点为二叉树叶子结点，但中序遍历还未结束
while (curt != null || !stack.empty()) {
while (curt != null) {
// 一直找，找到最左边结点，即中序遍历输出的第一个结点
stack.push(curt);
curt = curt.left;
}
// 此时当前结点的左儿子已经为空
curt = stack.pop();
result.add(curt.val);
/* 当前结点的右儿子如果为空，证明当前结点是叶子结点则会进入下一轮while循环，
* 当栈不为空时会 pop 出当前结点的根结点，curt 指向新的结点
*/
curt = curt.right;
}
return result;
}
}
https://leetcode.com/problems/binary-tree-inorder-traversal/solution/
- 遍历+递归
public class Solution {
/*
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> results = new ArrayList<>();
traversal(root, results);
return results;
}
private void traversal(TreeNode root, List<Integer> results) {
if (root == null) {
return;
}
traversal(root.left, results);
results.add(root.val);
traversal(root.right, results);
}
}
- 分治+递归
public class Solution {
/*
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> results = new ArrayList<>();
if (root == null) {
return results;
}
List<Integer> left = inorderTraversal(root.left);
List<Integer> right = inorderTraversal(root.right);
results.addAll(left);
results.add(root.val);
results.addAll(right);
return results;
}
}
http://blog.csdn.net/u012877472/article/details/49401751