1. question: 二叉树的中序遍历(简单)
给定一个二叉树的根节点 root ,返回它的 中序 遍历。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal
示例 1:
1 2
| 输入:root = [1,null,2,3] 输出:[1,3,2]
|
示例 2:
示例 3:
示例 4:
1 2
| 输入:root = [1,2] 输出:[2,1]
|
示例 5:
1 2
| 输入:root = [1,null,2] 输出:[1,2]
|
提示:
1 2
| 树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100
|
2. answers
和先序遍历一样,中序遍历也可以分用递归和非递归的方法解决。
2.1 递归解法
代码如下所示:
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
| public class Solution_0011 {
public static void recurive(TreeNode root, List<Integer> result){
if(root != null){ recurive(root.left, result); result.add(root.val); recurive(root.right, result); } }
public static List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
recurive(root, result);
return result; }
public static void main(String[] args) {
TreeNode tn1 = new TreeNode(3); TreeNode tn2 = new TreeNode(2, tn1, null); TreeNode root = new TreeNode(1, null, tn2);
List<Integer> integers = inorderTraversal(root);
for(Integer i : integers){ System.out.println(i); } } }
|
2.2 迭代解法
这里注意,迭代解法并不是和递归解法中那样调换根节点和左子树访问顺序那样简答。这是因为,我们在遍历二叉树的顺序和访问二叉树的顺序不一样。我们从上到下访问二叉树,肯定是先访问根节点,因为先序遍历也是先访问根节点,所以先序遍历的迭代方法比较简单。
而中序遍历,则是中间访问根节点,先访问左节点,直到左节点(左孩子)为空时,再访问根节点。同时我们还要保留之前的根节点以及右节点。
代码如下所示;
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
| public class Solution_0011 {
public static List<Integer> inorderTraversalPlus(TreeNode root) {
List<Integer> result = new ArrayList<>(); Stack<TreeNode> sta = new Stack<>();
while(root != null || !sta.isEmpty()){
if(root != null){ sta.push(root); root = root.left; } else { root = sta.pop(); result.add(root.val);
root = root.right; } }
return result; }
public static void main(String[] args) {
TreeNode tn1 = new TreeNode(3); TreeNode tn2 = new TreeNode(2, tn1, null); TreeNode root = new TreeNode(1, null, tn2);
List<Integer> integers = inorderTraversalPlus(root); for(Integer i: integers){ System.out.println(i); } } }
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。