题目描述:Given a binary tree, return the inorder traversal of its nodes’ values.
简单来说就是一个二叉树的中序遍历。题目下面有Note,要求不要采用递归的解法。这里递归的解法是最容易理解的,但是一方面是慢,另一方面是要占用大量的空间,容易爆栈。这里采用循环的方式解;
构建一个指针p,如果p不为空,那么将p入栈,p指向p的左节点;
如果p为空,说明已经走到尽头了,那么将栈顶弹出,加入结果集,并且访问右节点;
代码:
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Stack<TreeNode> stk = new Stack<>(); TreeNode p = root; while (p != null || !stk.empty()) { if(p != null) { stk.push(p); p = p.left; } else { p = stk.pop(); result.add(p.val); p = p.right; } } return result; } private class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
近期评论