二叉树算法之【中序遍历】

目录

LeetCode-94题

LeetCode-94题

给定一个二叉树的根节点root，返回它的中序遍历结果。 

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();order(root, result);return result;}private void order(TreeNode root, List<Integer> mid) {//当前节点TreeNode curr = root;//借助栈LinkedList<TreeNode> stack = new LinkedList<>();//最近一次pop的元素TreeNode pop = null;while (curr != null || !stack.isEmpty()) {if (curr != null) {stack.push(curr);//待处理左节点curr = curr.left;} else {//栈不为空TreeNode peek = stack.peek();//右节点为空if (peek.right == null) {mid.add(peek.val);pop = stack.pop();}//右节点处理完else if (peek.right == pop) {pop = stack.pop();}//处理右节点else {mid.add(peek.val);curr = peek.right;}}}}
}