[数据结构与算法]二叉树数组求前中后序遍历

题目描述

对给定的二叉树依次完成前序，中序，后序遍历，并输出遍历结果。
每行输入为一个二叉树，一维数组形式。其中-1表示Nil节点，例如：1,7,2,6,-1,4,8 构成的二叉树如下图所示：
[1,7,2,6,-1,4,8], 其中-1为null节点，不用输出。

示例

Input：[1,7,2,6,-1,4,8]
Output：[[], [], []]
输出形式：【【前序遍历】、【中序遍历】、【后序遍历】】

方法一：公式法

利用当前节点与其左节点和右节点的公式即可求解。设a为当前节点下标，则公式如下：
当前节点的左节点的下标：a * 2 + 1
当前节点的右节点的下标：a * 2 + 2

results = [[]for i in range(3)]
class Solution:
    def binaryTreeScan(self , input ):
        # write code here
        # 前序遍历
        def preOrder(root):
            if root<len(input):
                if input[root]!=-1:
                    results[0].append(input[root])
                preOrder(root*2+1)
                preOrder(root*2+2)
        # 中序遍历
        def inOrder(root):
            if root<len(input):
                inOrder(root*2+1)
                if input[root]!=-1:
                    results[1].append(input[root])
                inOrder(root*2+2)
        # 后序遍历
        def postOrder(root):
            if root<len(input):
                postOrder(root*2+1)
                postOrder(root*2+2)
                if input[root]!=-1:
                    results[2].append(input[root])
        preOrder(0)
        inOrder(0)
        postOrder(0)
        return results

方法二：构造二叉树

构造二叉树，然后利用递归分别计算

class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
 
struct TreeNode
{
  TreeNode *left;
  TreeNode *right;
  int val;
  TreeNode(){};
  TreeNode(int v) : val(v), left(nullptr), right(nullptr){};
};
//前序遍历
void qTravel(TreeNode *root)
{
  if (root==nullptr)
    return;
  path.push_back(root->val);
  qTravel(root->left);
  qTravel(root->right);
}
//中序遍历
void zTravel(TreeNode *root)
{
  if (root==nullptr)
    return;
 
  zTravel(root->left);
  path.push_back(root->val);
  zTravel(root->right);
}
//后续遍历
void hTravel(TreeNode *root)
{
  if (root==nullptr)
    return;
  hTravel(root->left);
  hTravel(root->right);
  path.push_back(root->val);
}
//数组建立二叉树
void create_tree(TreeNode *&tree, int a[], int len, int index)
{
  if (index >= len)
    return;
  if (a[index] == -1)
    return;
  tree = new TreeNode();
  tree->val = a[index];
  tree->left = nullptr;
  tree->right = nullptr;
  create_tree(tree->left, a, len, 2 * index + 1);
  create_tree(tree->right, a, len, 2 * index + 2);
}
 
 
 
vector<vector<int>> binaryTreeScan(int *input, int inputLen)
{
 
  TreeNode *root;
  create_tree(root, input, inputLen, 0);
 
  qTravel(root);
  ans.push_back(path);
 
  path.clear();
 
  zTravel(root);
  ans.push_back(path);
     
 
  path.clear();
 
  hTravel(root);
  ans.push_back(path);
 
  path.clear();
  return ans;
}
 
};