题解 | #二叉树的中序遍历#

秒懂【二叉树中序遍历】！递归一步步拆解。

1.思路

需要先明确二叉树【中序】遍历的规则：

二叉树的遍历一般使用【递归】的方法。如果要采用递归方法需满足递归的2个条件：

可以看出，对于左子树、右子树的遍历操作与整个二叉树一样，只是数据规模不同。

对于整颗二叉树来说，叶子节点左右子树都是Null，满足递归的第二个条件：不能无限循环，有终止条件（节点为Null）。因此可以使用递归来完成二叉树的中序遍历。

这时，就可以依据前序遍历的规则写出递推公式与伪代码：

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        res = []
        self.midOrder(res, root)
        return res

    def midOrder(self, res, root):
        # 2. 递归终止条件：遇到空节点则返回
        if root is None:
            return

        # 1.问题分解（递推公式）
        # 1.1 先左子树
        self.midOrder(res, root.left)
        # 1.2 再访问根节点
        res.append(root.val)
        # 1.3 最后去右子树
        self.midOrder(res, root.right)

2.2 Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();
        inOrder(list, root);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void inOrder(List<Integer> list, TreeNode root) {
        // 2. 递归终止条件：遇到空节点则返回
        if (root == null) {
            return;
        }

        // 1. 问题分解（递推公式）
        // 1.1 先左子树
        inOrder(list, root.left);
        // 1.2 再访问根节点
        list.add(root.val);
        // 1.3 最后去右子树
        inOrder(list, root.right);
    }
}

2.3 Go代码

package main

import . "nc_tools"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return int整型一维数组
 */
func inorderTraversal(root *TreeNode) []int {
	// write code here
	list := make([]int, 0)
	midOrder(&list, root) //注意：传递的是切片对应的指针（切片的地址），否则会变成值传递，最后返回空切片
	return list
}

func midOrder(list *[]int, root *TreeNode) {
	// 2. 递归终止条件：遇到空节点则返回
	if root == nil {
		return

	}

	// 1. 问题分解（递推公式）
	// 1.1 先左子树
	midOrder(list, root.Left)
	// 1.2再访问根节点
	*list = append(*list, root.Val)
	// 1.3 最后去右子树
	midOrder(list, root.Right)
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构