二叉树链式结构刷题训练：遍历与单值树判定

一、二叉树的遍历

在链式二叉树的定义与实现中我们已经详细讲解了二叉树常见的三种遍历方式，以及层序遍历。

前序遍历：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

二、单值二叉树

题目链接：https://leetcode.cn/problems/univalued-binary-tree/description/

这道题要求我们查看一颗二叉树里面所有节点存放的值是否相同，考察链式二叉树中递归的学习以及对遍历的理解。

解析思路：使用递归思想，将大问题转化为子问题。判断根节点和左右子树根节点是否相同，如果相同则继续判断左右子树是否同时为单值二叉树。或者理解为遍历整颗二叉树时，每遍历一个节点就判断一下当前节点和它的左右孩子是否相等（需先判断左右孩子是否存在）。

具体做法：首先判断根节点是否为空，如果为空返回 true；如果不为空，先判断左右孩子是否为空，跟不为空的孩子做比较，如果发现某个孩子的值和根节点不同，就返回 false；如果和左右孩子比较后发现相同，则递归左右孩子，将整颗子树是否是单值二叉树问题转化为左子树和右子树是否同时为单值二叉树。

bool isUnivalTree(struct TreeNode* root){
    // 首先判断根节点是否为空，为空返回 true
    if (root == NULL) {
        return true;
    }
    // 如果左孩子不为空，看看左孩子和根节点是否相同，不同就返回假
    if (root->left && root->left->val != root->val) {
        return false;
    }
    
     (root->right && root->right->val != root->val) {
         ;
    }
    
     left = (root->left);
     right = (root->right);
    
     left && right;
}