遍历二叉树

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct TreeNode {
  ElemType data;
  struct TreeNode* left;
  struct TreeNode* right;
} TreeNode, *PTreeNode;

// ==================== function declaration ====================
PTreeNode construct(int* preorder, int* inorder, int i, int j, int n);
void collectLeaves(PTreeNode root, int* leaves, int* leavesSize);

int main(const int argc, const char* const argv[]) {
  int n;
  fscanf(stdin, "%d", &n);
  
  int preorder[n], inorder[n];
  int i;
  for (i = 0; i < n; ++i)
    fscanf(stdin, "%d", preorder + i);
  for (i = 0; i < n; ++i)
    fscanf(stdin, "%d", inorder + i);
  
  PTreeNode root = construct(preorder, inorder, 0, 0, n);
  int leaves[n], leavesSize = 0;
  collectLeaves(root, leaves, &leavesSize);
  
  // dynamic programming
  int dp2 = 0, dp1 = 0;
  for (i = 0; i < leavesSize; ++i) {
    int dp = fmax(dp2 + *(leaves + i), dp1);
    dp2 = dp1;
    dp1 = dp;
  }
  
  return fprintf(stdout, "%d", dp1), 0;
}

PTreeNode construct(int* preorder, int* inorder, int i, int j, int n) {
  if (n <= 0) return NULL;
  PTreeNode root = (PTreeNode) malloc(sizeof(TreeNode));
  if (!root) return root;
  root->data = *(preorder + i);
  root->left = root->right = NULL;
  if (n == 1) return root;
  
  int k = j;
  while (*(inorder + k) != *(preorder + i)) ++k;
  int l = k - j;
  
  root->left  = construct(preorder, inorder, i + 1, j, l);
  root->right = construct(preorder, inorder, i + 1 + l, k + 1, n - 1 - l);
  return root;
}

void collectLeaves(PTreeNode root, int* leaves, int* leavesSize) {
  if (!root) return;
  if (!root->left && !root->right) {
    *(leaves + (*leavesSize)++) = root->data;
    return;
  }
  collectLeaves(root->left,  leaves, leavesSize);
  collectLeaves(root->right, leaves, leavesSize);
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> getLeavesByPreOrder(const int& n, int i = 0) {	//根据前序遍历确定叶节点
	static vector<int> leaves;
	int temp;
	cin >> temp;
	if ((i << 1) + 1 >= n) {								//添加叶节点
		leaves.push_back(temp);
		return leaves;
	}
	getLeavesByPreOrder(n, (i << 1) + 1);
	getLeavesByPreOrder(n, (i << 1) + 2);
	return leaves;
}
int main() {
	int n;
	cin >> n;
	vector<int> leaves = getLeavesByPreOrder(n);
	vector<int> dp(leaves.size());
	dp[0] = leaves[0];
	dp[1] = max(leaves[0], leaves[1]);
	for (int i = 2; i < dp.size(); i++)
		dp[i] = max(dp[i - 2] + leaves[i], dp[i - 1]);
	cout << dp.back();
	return 0;
}

using namespace std;
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

static int tree[100000];
static int dp[100000];
static void getTree(int lvl, int target, int* plen)
{
    int t;
    if (lvl >= target)
    {
        cin >> tree[(*plen)++];
        return;
    }
    else
    {
        cin >> t;
        getTree(lvl + 1, target, plen);
        getTree(lvl + 1, target, plen);
    }
}
static inline int max(int x, int y)
{
    return x > y ? x : y;
}
int main()
{
    int n, k, i, len, tmp;
    while (cin >> n)
    {
        k = n + 1;
        i = 0;
        while (k > 1)
        {
            k >>= 1;
            i++;
        }
        k = i;
        len = 0;
        getTree(0, k - 1, &len);
        for (i = 0; i < n; i++)
            cin >> tmp;
        dp[0] = tree[0];
        dp[1] = tree[1];
        dp[2] = tree[2] + dp[0];
        for (i = 3; i < len; i++)
            dp[i] = tree[i] + max(dp[i - 2], dp[i - 3]);
        if (len <= 1)
            cout << dp[len - 1];
        else
            cout << max(dp[len - 1], dp[len - 2]);
        cout << endl;
    }
    return 0;
}