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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

	/**
	 * 前序遍历
	 */
	public List<Integer> preOrderStack(TreeNode root) {
		List<Integer> res = new LinkedList<>();
		Stack<TreeNode> stack = new Stack<>();
		while (root != null || !stack.isEmpty()) {
			// 将根节点添加到结果集中，并将根节点添加到栈中
			while (root != null) {
				stack.push(root);
				res.add(root.val);
				root = root.left;
			}
			root = stack.pop();
			root = root.right;
		}
		return res;
	}

	/**
	 * 中序遍历
	 */
	public List<Integer> inOrderStack(TreeNode root) {
		List<Integer> res = new LinkedList<>();
		Stack<TreeNode> stack = new Stack<>();

		while (root != null || !stack.isEmpty()) {
			//将左节点放入栈中，直至没有左节点为止，此时root为null
			while (root != null) {
				stack.push(root);
				root = root.left;
			}
			//最左节点
			root = stack.pop();
			res.add(root.val);
			// 从最左节点向上遍历右节点
			root = root.right;
		}
		return res;
	}

	/**
	 * 后序遍历
	 */
	public static List<Integer> postOrderStack(TreeNode root) {
		List<Integer> res = new LinkedList<>();
		Stack<TreeNode> stack = new Stack<>();
		//保存上一次访问右子树的值，这样就可以判断右子树是否访问过
		TreeNode prev = null;
		while (root != null || !stack.isEmpty()) {
			//将左子树添加到栈中
			while (root != null) {
				stack.push(root);
				root = root.left;
			}
			root = stack.pop();
			// 这时需要判断右子树是否被访问过
			if (root.right == null || prev == root.right) {
				//没有右子树，或者已经访问过
				res.add(root.val);

				prev = root;
				root = null;
			} else {
				//未访问过
				stack.push(root);
				root = root.right;
			}
		}
		return res;
	}

 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

	/**
	 * 前序遍历，遍历顺序为：根节点，左节点，右节点
	 */
	public List<Integer> preOrder(TreeNode root) {
		List<Integer> res = new LinkedList<>();
		preOrderHelp(root, res);
		return res;
	}

	public void preOrderHelp(TreeNode node, List<Integer> res) {
		if (node == null) {
			return;
		}
		res.add(node.val);
		preOrderHelp(node.left, res);
		preOrderHelp(node.right, res);
	}
	
	/**
	 * 中序遍历，遍历顺序为：左节点，根节点, 右节点
	 */
	public List<Integer> inOrder(TreeNode root) {
		List<Integer> res = new LinkedList<>();
		inOrderHelp(root, res);
		return res;
	}

	public void inOrderHelp(TreeNode node, List<Integer> res) {
		if (node == null) {
			return;
		}
		inOrderHelp(node.left, res);
		res.add(node.val);
		inOrderHelp(node.right, res);
	}



	/**
	 * 后序遍历，遍历顺序为：左节点，右节点，根节点
	 *
	 * @param root
	 * @return
	 */
	public List<Integer> postOrder(TreeNode root) {
		List<Integer> res = new LinkedList<>();
		postOrderHelp(root, res);
		return res;
	}

	public void postOrderHelp(TreeNode node, List<Integer> res) {
		if (node == null) {
			return;
		}
		postOrderHelp(node.left, res);
		postOrderHelp(node.right, res);
		res.add(node.val);
	}