二叉树三种遍历与对称判定的实现

文章配图

本节围绕二叉树的常见 OJ 题展开，涵盖前序遍历、单值二叉树判定和对称二叉树判定三类问题，帮助建立递归操作二叉树的思维方式。

大部分人学算法都是这个循环：听懂 → 过段时间忘光 → 重新看懂 → 慢慢内化，能力一点点涨。

文章配图

二叉树前序遍历

题目要求返回一个指针，通过指针访问数组元素。显然需要创建一个指针作为数组的首地址。returnSize 是输出参数（指针），判题工具会根据这个形参的值来判断结果是否正确——它作为数组下标，将遍历好的节点值一一放入目标数组。

LeetCode 题目里的形参都有它具体的意思，题做多了就认得了。

文章配图

void dfs(struct TreeNode* node, int* result, int* returnSize){
    if(node == NULL){
        return;
    }
    result[(*returnSize)++] = node->val;
    dfs(node->left, result, returnSize);
    dfs(node->right, result, returnSize);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* result =(int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    dfs(root, result, returnSize);
    return result;
}

具体讲解：
– 因为是数组要用到指针，所以需要 malloc（没 malloc 该指针只能储存一个数据）
– 利用 returnSize 作为下标将二叉树的节点一一插入，所以解引用赋值为 0
– dfs 的形参包含二叉树节点、数组和下标，根据前序排列将数据插入数组

二叉树的题型一般都会考虑到当首节点为 NULL 时直接 return。这就是前序遍历的方法 ELR（根-左-右）：

文章配图

result[(*returnSize)++] = node->val;
dfs(node->left, result, result, returnSize);
dfs(node->right, result, returnSize);

优先级注意：(*returnSize)++ 若是没括号就是给指针加加。*returnSize++ 先加加再解引用。++*returnSize 先解引用再加加。

中序遍历（LRA）和后序遍历（LRA）的代码结构类似，只改变插入顺序：

文章配图

中序遍历 LRA（左-根-右）：

dfs(node->left, result, returnSize);
result[(*returnSize)++] = node->val;
dfs(node->right, result, returnSize);

后序遍历 LRA（左-右-根）：

文章配图

dfs(node->left, result, returnSize);
dfs(node->right, result, returnSize);
result[(*returnSize)++] = node->val;

sizeof(int) * 100 是因为题目要求二叉树节点不超过 100 个。

单值二叉树

文章配图

判断一棵二叉树是否为单值二叉树，即所有节点的值都相同。思路是递归检查每个节点的左右子节点是否等于根节点的值。

bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL){
        return true;
    }

    if(root->left && root->left->val != root->val){
        return false;
    }
    if(root->right && root->right->val != root->val){
        return false;
    }
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

头节点为 NULL 即视为单值二叉树，返回 true
判断目标节点的左右节点是否等于头节点的值
用递归遍历左右两树杈是否符合规则
&& 的作用：只有左右两边为真才为真。利用递归函数和 &&，只要有一个不符合规则就会返回 false

补充 ||：两个为真才为真，两个为假才为假，一假一真为真。

递归的关键是看最后一步 return 的返回值，然后倒推上一个函数的返回值。

对称二叉树

判断一棵二叉树是否对称，需要比较左子树和右子树是否镜像对称。

bool check(struct TreeNode* left, struct TreeNode* right){
    if(left == NULL && right == NULL){
       return true;
    }
    if(left == NULL || right == NULL){
       return false;
    }
    if(left->val != right->val){
       return false;
    }

   return check(left->left, right->right) && check(left->right, right->left);
}

bool isSymmetric(struct TreeNode* root) {
   if(root == NULL){
       return true;
   }
   return check(root->left, root->right);
}

头节点为 NULL 即为对称二叉树，返回 true
check 函数的形参为左右节点指针
left == NULL && right == NULL：当只有一个节点时为对称二叉树返回 true；当全对比完后说明符合规则也返回 true
left == NULL || right == NULL：只有一个为空说明不对称，返回 false
核心比较：check(left->left, right->right) && check(left->right, right->left)——左子树的左与右子树的右比较，左子树的右与右子树的左比较。这样递归就可以符合对称二叉树的规则