给定一个二叉树,返回它的中序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2] 进阶: 递归算法很简单,你可以通过迭代算法完成吗? 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解:
/** * 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) { if (root == null) { return new ArrayList<>(); } Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; List<Integer> list = new ArrayList<>(); while (stack.size() > 0 || cur != null) { while (cur != null) { stack.push(cur); cur = cur.left; } TreeNode node = stack.pop(); list.add(node.val); cur = node.right; } return list; } }
分析: 利用栈,节点按先序遍历进行入队,然后从栈中弹出节点,然后再指向右节点。