Given a binary tree, return the inorder traversal of its nodes‘ values.
Example:
Input: [1,null,2,3]
1
2
/
3
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
方法一：递归
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public void preorderTraversal(TreeNode root) { if(root==null) return ; preorderTraversal(root.left); System.out.print(root.val+‘ ‘); preorderTraversal(root.right); } }
方法二：迭代
中序遍历第左右根，所以设计程序时首先要考虑的是找到最左边的叶子结点。找到之后弹出还要考虑这个结点有没有右孩子。
/** * 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) { Stack<TreeNode> stack=new Stack<TreeNode>(); List<Integer> list=new ArrayList<Integer>(); while (root!=null||!stack.isEmpty()){ while (root!=null){ stack.add(root); root=root.left; } TreeNode treeNode=stack.pop(); list.add(treeNode.val); root=treeNode.right; //root是判断条件。每次弹出的结点都要检查是否还有右孩子。有就加入，没有就弹出。 } return list; } }
94. Binary Tree Inorder Traversal（非递归实现二叉树的中序遍历）
原文：https://www.cnblogs.com/shaer/p/10670452.html