- 1、题目描述:
-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