NC45实现二叉树先序，中序和后序遍历（视频+三种语言讲解）

- 1、题目描述：

- 2、题目链接： https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=117&tqId=37819&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

-3、 设计思想：

-4、视频讲解链接B站视频讲解

-5、代码： c++版本:

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
	 vector<int> pre;
	 vector<int> in;
	 vector<int> post;
	     /*先序遍历*/
     void preOrderRecur(TreeNode *root) {
        if (root == nullptr) return;
        pre.push_back(root->val);//根
        preOrderRecur(root->left);//左
        preOrderRecur(root->right);//右
    }
     /*中序遍历*/
     void inOrderRecur(TreeNode *root) {
        if (root == nullptr) return;
        inOrderRecur(root->left);//左
        in.push_back(root->val);//根
        inOrderRecur(root->right);//右
    }
     /*后序遍历*/
     void posOrderRecur(TreeNode *root) {
        if (root == nullptr) return;
        posOrderRecur(root->left);//左
        posOrderRecur(root->right);//右
        post.push_back(root->val);//根
    }
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
		vector<vector<int>>res;//用于返回最终的结果
		preOrderRecur(root);//先序遍历
        inOrderRecur(root);//中序遍历
        posOrderRecur(root);//后序遍历
        res.push_back(pre);//将先序遍历放进res
        res.push_back(in);//将中序遍历放进res
        res.push_back(post);//将后序遍历放进res
        return res;
    }
};

Java版本：

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    ArrayList<Integer> pre = new ArrayList<Integer>();//存储先序遍历结果
    ArrayList<Integer> in = new ArrayList<Integer>();//存储中序遍历结果
    ArrayList<Integer> post = new ArrayList<Integer>();//存储后序遍历结果
    public int[][] threeOrders (TreeNode root) {
        // write code here
        
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        preOrderRecur(root);
        inOrderRecur(root);
        posOrderRecur(root);
        res.add(new ArrayList(pre));
        res.add(new ArrayList(in));
        res.add(new ArrayList(post));
        int [][]ans = new int[res.size()][res.get(0).size()];
        for(int i = 0;i < res.size();i ++){
            for(int j = 0;j < res.get(0).size();j ++){
                ans[i][j] = res.get(i).get(j);
            }
        }
        return ans;
    }
    
    /*先序遍历*/
    public void preOrderRecur(TreeNode root) {
        if (root == null) return;
        pre.add(root.val);//根
        preOrderRecur(root.left);//左
        preOrderRecur(root.right);//右
    }
     /*中序遍历*/
    public void inOrderRecur(TreeNode root) {
        if (root == null) return;
        inOrderRecur(root.left);//左
        in.add(root.val);//根
        inOrderRecur(root.right);//右
    }
     /*后序遍历*/
    public void posOrderRecur(TreeNode root) {
        if (root == null) return;
        posOrderRecur(root.left);//左
        posOrderRecur(root.right);//右
        post.add(root.val);//根
    }
}

Python版本:

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 the root of binary tree
# @return int整型二维数组
#
class Solution:
    #先序遍历
    pre,inn,post=[],[],[]#分别用来存储先序遍历结果、中序遍历结果、后序遍历结果
    def preOrderRecur(self ,root):
        if root == None: return
        self.pre.append(root.val)#根
        self.preOrderRecur(root.left)#左
        self.preOrderRecur(root.right)#右

    #中序遍历
    def inOrderRecur(self ,root):
        if (root == None) :return
        self.inOrderRecur(root.left)#左
        self.inn.append(root.val)#根
        self.inOrderRecur(root.right)#右
    
    #后序遍历
    def posOrderRecur(self , root):
        if (root == None) :return
        self.posOrderRecur(root.left)#左
        self.posOrderRecur(root.right)#右
        self.post.append(root.val)#根
    
    def threeOrders(self , root ):
        # write code here
        res = []
        self.preOrderRecur(root)#先序遍历
        self.inOrderRecur(root)#中序遍历
        self.posOrderRecur(root)#后序遍历
        res.append(self.pre)#将先序遍历放进res
        res.append(self.inn)#将中序遍历放进res
        res.append(self.post)#将后序遍历放进res
        return res