【数据结构篇】树的遍历

树的遍历

前序遍历

• 首先访问根节点，然后遍历左子树，最后遍历右子树

  递归写法

  void preTravel(struct TreeNode*root)
  {
      if(root!=NULL)
      {
          printf("%d",root->val);
          travel(root->left);
          travel(root->right);
      }
  }

  迭代写法 (迭代就是把递归过程中调用的栈显式表达出来)

  void preTravel(struct TreeNode*root)
  {
      struct TreeNode *stk[100];
      int stk_top = -1;
      while (stk_top > -1 || root != NULL) 
      {
          while (root != NULL) 
          {
              printf("%d",root->val);
              stk[++stk_top] = root;
              root = root->left;
          }
          root = stk[stk_top--];
          root = root->right;
      }
  }

中序遍历

• 先左后根最后右（==二叉搜索树中可以得到递增的有序序列==）

  递归写法

  void inorderTravel(struct TreeNode*root)
  {
       if(root==NULL)
          return;
      inorderTravel(root->left);
      printf("%d",root->val);
      inorderTravel(root->right);
  }

  迭代写法 (迭代就是把递归过程中调用的栈显式表达出来)

  void inorderTravel(struct TreeNode*root)
  {
      struct TreeNode *stk[100];
      int stk_top = -1;
      while (stk_top > -1 || root != NULL) 
      {
          while (root != NULL) 
          {
              stk[++stk_top] = root;
              root = root->left;
          }
          root = stk[stk_top--];
          printf("%d",root->val);
          root = root->right;
      }
  }

后序遍历

• 先左后右最后根

  递归写法

   void postTravel(struct TreeNode*root)
  {
       if(root==NULL)
          return;
      postTravel(root->left,a,returnSize);
      printf("%d",root->val);
      postTravel(root->right,a,returnSize);
  }

  迭代写法

  void preTravel(struct TreeNode*root)
  {
      struct TreeNode *stk[100];
      struct TreeNode *prev = NULL;
      int stk_top = -1;
      if(root==NULL)
          return;
      while (stk_top > -1 || root != NULL) 
      {
          while (root != NULL) 
          {
              stk[++stk_top] = root;
              root = root->left;
          }
          root=stk[stk_top--];
          if (root->right == NULL || root->right == prev) {
              printf("%d",root->val);
              prev = root;
              root = NULL;
          } 
          else 
          {
              stk[top++] = root;
              root = root->right;
          }
      }
  }

层序遍历

• 用队列实现广度优先搜索，逐层遍历

#define MAX 2000
int **levelOrder(struct TreeNode*root,int *returnSize,int **returnColumnSize)
{//返回逐层遍历的二维数组，returnColumnSize记录每一层的大小
    *returnSize=0;//层数
    if(root==NULL)
        return;
    int**res=(int**)malloc(sizeof(int*)*MAX);//申请一个二维数组空间
    struct TreeNode*Q[MAX];//队，存放所有结点
    *returnColumnSize=(int*)malloc(sizeof(int)*MAX);
    int flag,size,front=0,rear=0;
    struct TreeNode*tmp=NULL;
    Q[rear++]=root;
    while(front!=rear)
    {//队列不空时
        flag=rear;//当前层尾指针
        size=0;//当前层数组大小
        res[*returnSize]=(int*)malloc(sizeof(int*)*(flag-front));
        while(front<flag)
        {//处理当前层
            tmp=Q[front++];
            res[*returnSize][size++]=tmp->val;
            //每个结点的左右孩子入队
            if(p->left)
                Q[rear++]=p->left;
            if(p->right)
                Q[rear++]=p->right;
        }
        (*returnColumnSize)[*returnSize]=size;
        returnSize++;
    }
    return res;
}

递归解决问题

• 最大深度

int maxDepth(struct TreeNode* root){
     return root == NULL ? 0 :fmax(maxDepth(root->left), maxDepth(root->right))+ 1;
}

• 对称二叉树

bool isMirror(struct TreeNode*p,struct TreeNode*q)
{//递归思想：如果对称，那每个树的右子树镜像对称另一个树的左子树
    if(!p&&!q)
        return true;
    if(!p||!q)
        return false;
    return (p->val==q->val)&&(isMirror(p->left,q->right))&&(isMirror(p->right,q->left));
}
bool isSymmetric(struct TreeNode* root){
    return isMirror(root,root);
}

• 路径总和

//判断二叉树中是否有一条路径节点之和等于目标值
bool hasPathSum(struct TreeNode* root, int targetSum){
    if(!root)
        return false;
    if(!root->left&&!root->right)
        return root->val==targetSum;
    return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);
}

• 最近公共祖先

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    struct TreeNode* ancestor=root;
    while(1)
    {
        if(p->val<ancestor->val&&q->val<ancestor->val)
            ancestor=ancestor->left;
        else if(p->val>ancestor->val&&q->val>ancestor->val)
            ancestor=ancestor->right;
        else
            break;
    }
    return ancestor;
}

• 最长路径

#include <stdio.h>
#include <string.h>

using namespace std;

const int N = 100010;

int e[N] , ne[N] , h[N] , idx;
int f[N];//f[u]表示u到最远叶节点的距离。显然如果u是节点，则f[u]=0。
int n , m , ans;

void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx++;
}

void dfs(int u)//求以u为根节点到叶节点的最大距离
{
    int a = 0 , b = 0;//a记录u到最远叶节点的距离，b记录u到次远叶节点的距离
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        //求子节点j到最远叶节点的距离
        dfs(j);

        int t = f[j] + 1;//u通过j能到的最远叶节点的距离

        //更新a、b
        if(t >= a)
            b = a , a = t;
        else if(t > b)
            b = t;
    }

    f[u] = a;
    //最后的答案就是u所能到的最远叶节点距离和次远叶节点距离之和
    ans = max(ans , a + b);
}

int main()
{
    cin >> n >> m;

    memset(h , -1 , sizeof h);
    //电脑其实和交换机等价，所以电脑的标号从n继续往后标记即可
    for(int i = 2 ; i <= n + m ; i++)
    {
        int j;
        cin >> j;
        add(j , i);//因为是自根向下DP，所以建一条边即可。
    }

    dfs(1);

    cout << ans << endl;
}