LeetCode - Algorithms - 94. Binary Tree Inorder Traversal

2007年学习数据结构曾经用Java实现过，虽然还是知其然而不知其所以然，北大那本《数据结构与算法》(张铭、赵海燕、王腾蛟)教材上是用C++实现的。

非递归深度优先周游二叉树

  • 栈是实现递归的最常用的结构
  • 深度优先二叉树周游是递归定义的
  • 利用一个栈来记下尚待周游的结点或子树，以备以后访问。

非递归中序周游二叉树

  • 遇到一个结点，就把它推入栈中，并去周游它的左子树
  • 周游完左子树后，从栈顶托出这个结点并访问之，然后按照它的右链接指示的地址再去周游该结点的右子树。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
    	List<Integer> list = new ArrayList<Integer>();
		if (root!=null) {
			TreeNode ptr = root;
			Stack<TreeNode> stk = new Stack<TreeNode>();
			while(!stk.isEmpty() || ptr != null) {
				if (ptr!=null) {
					stk.push(ptr);
					ptr = ptr.left;
				}
				else {
					ptr = (TreeNode) stk.peek();
					list.add(ptr.val);
					ptr = ptr.right;
					stk.pop();
				}
			}			
		}
		return list;        
    }
}

Submission Detail

  • 68 / 68 test cases passed.
  • Runtime: 1 ms
  • Your runtime beats 60.69 % of java submissions.