网站开发后端书籍上海 网站建设 外包

题目 

思路

使用一个栈来模拟递归的过程，以非递归的方式完成中序遍历(使用栈可以避免递归调用的空间消耗)。

遍历顺序步骤：

1. 遍历左子树
2. 访问根节点
3. 遍历右子树

package algorithm_leetcode;import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class Solution_94 {public List<Integer> inorderTraversal(TreeNode root) {// 待处理节点Stack<TreeNode> stack = new Stack<>();// 结果List<Integer> output_arr = new ArrayList<>();// 如果root为空if (root == null) {// 返回空的 output_arrreturn output_arr;}// 初始化为根节点TreeNode current = root;// 循环 只要当前节点不为空，并且栈不为空 while (current != null || !stack.isEmpty()) {// 当前节点不为空，直到左子树为空while (current != null) {// 添加到栈stack.push(current);// 当前节点移动到左子节点current = current.left;}// 弹出栈节点current = stack.pop();// 添加到结果中output_arr.add(current.val);// 如果有右子节点，就移动到右子节点current = current.right;}return output_arr;}
}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;}
}