目录

零、自定义二叉树

一、二叉树的遍历

144. 二叉树的前序遍历

145. 二叉树的后序遍历

94. 二叉树的中序遍历

589. N 叉树的前序遍历

102. 二叉树的层序遍历

226. 翻转二叉树

二、二叉树的属性

101. 对称二叉树

572. 另一棵树的子树

111. 二叉树的最小深度

222. 完全二叉树的节点个数 

110. 平衡二叉树

零、自定义二叉树

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

---

一、二叉树的遍历

144. 二叉树的前序遍历

    vector preorderTraversal(TreeNode* root) {
        vector res;
        traversal(root, res);
        return res;
    }
    void traversal(TreeNode* root, vector& v) {
        if (root == NULL)   return;
        v.push_back(root->val);
        traversal(root->left, v);
        traversal(root->right, v);
    }

145. 二叉树的后序遍历

    vector postorderTraversal(TreeNode* root) {
        vector res;
        traversal(root, res);
        return res;
    }
    void traversal(TreeNode* root, vector& v) {
        if (root == NULL)   return;    
        traversal(root->left, v);       
        traversal(root->right, v);
        v.push_back(root->val);
    }

94. 二叉树的中序遍历

    vector inorderTraversal(TreeNode* root) {
        vector res;
        traversal(root, res);
        return res;
    }
    void traversal(TreeNode* root, vector& v) {
        if (root == NULL)   return;    
        traversal(root->left, v);
        v.push_back(root->val);
        traversal(root->right, v);      
    }

递归算法三要素：

1.  确定递归函数的参数和返回值： 即递归过程中需要处理的量；
2. 确定终止条件：防止溢出；
3. 确定单层递归的逻辑： 即每次递归需要处理的信息。

589. N 叉树的前序遍历

class Node {
public:
    int val;
    vector children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector _children) {
        val = _val;
        children = _children;
    }
};

    vector preorder(Node* root) {
        vector res;
        traversal(root, res);
        return res;
    }

    void traversal(Node* node, vector& nums) {
        if (node == NULL)   return;
        nums.push_back(node->val);
        if (!node->children.empty()) {
            for (auto i : node->children) {
                traversal(i, nums);
            }
        } 
    }

102. 二叉树的层序遍历

vector> levelOrder(TreeNode* root) {
        vector> res;
        queue nodeQueue;
        if(root != NULL) nodeQueue.push(root);
        while (!nodeQueue.empty()) {
            int sizeLevel = nodeQueue.size();
            vector valueLevel(sizeLevel);
            for (int i = 0; i < sizeLevel; i++) {
                valueLevel[i] = nodeQueue.front()->val;
                if (nodeQueue.front()->left) nodeQueue.push(nodeQueue.front()->left);
                if (nodeQueue.front()->right)  nodeQueue.push(nodeQueue.front()->right);
                nodeQueue.pop();
            }
            res.push_back(valueLevel);
        }
        return res;
    }

层序遍历用队列实现，每次出队前，入队该结点的左右孩子结点。

层序遍历相关题目：

• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度

226. 翻转二叉树

    TreeNode* invertTree(TreeNode* root) {
        invert(root);
        return root;
    }

    void invert(TreeNode* node) {
        if (node == NULL)   return;
        invert(node->left);
        invert(node->right);
        TreeNode* temp = node->left;
        node->left = node->right;
        node->right = temp;
    }

本题采用递归法，这道题前序遍历和后序遍历都可以，但中序遍历不行。否则交换完左孩子的左右孩子，再交换该结点的左右孩子，最后交换该结点右结点的左右孩子时，右结点实际上是之前的左结点。 

---

二、二叉树的属性

101. 对称二叉树

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

    bool compare(TreeNode* nodeLeft, TreeNode* nodeRight) {
        if (!nodeLeft && nodeRight)  return false;
        else if (nodeLeft && !nodeRight)  return false;
        // 没有左/右孩子节点时，当前递归返回true
        else if (!nodeLeft && !nodeRight)   return true;
        else if (nodeLeft->val != nodeRight->val)   return false;
        // 当前节点相等时，继续递归
        bool isSameOutside = compare(nodeLeft->left, nodeRight->right);
        bool isSameInside = compare(nodeLeft->right, nodeRight->left);
        return isSameOutside && isSameInside;
    }

本题采用递归法，对左侧子树采用左右中的遍历方式，对右侧子树采用右左中的遍历方式。若子树不对称，利用isSameOutside && isSameInside一直向上传递false的结果，直至返回最终结果。

1. 递归函数的参数和返回值：要比较的是两个树，从而参数是左子树节点和右子树节点，返回值是bool类型；
2. 确定终止条件：结点为空/结点都不空；
3. 单层递归逻辑：单层递归逻辑用于处理左右结点都不为空，且数值相同的情况。

本题也可以采用迭代法实现，利用队列保存待比较的数值【注意入队顺序】，代码如下：

bool isSymmetric(TreeNode* root) {
        if (root == NULL)    return true;
        queue leftAndRight;
        leftAndRight.push(root->left);
        leftAndRight.push(root->right);
        while (!leftAndRight.empty()) {
            TreeNode* left = leftAndRight.front();
            leftAndRight.pop();
            TreeNode* right = leftAndRight.front();
            leftAndRight.pop();
            // 左右都为空，继续判断
            if (!left && !right)   continue;
            // 左不存在或右不存在，返回false
            else if (!left || !right)    return false;
            // 左右都存在但不相等，返回false
            else if (left->val != right->val)  return false;
            // 左右都存在且相等，入队左右孩子(注意顺序)，继续下一次迭代
            leftAndRight.push(left->left);
            leftAndRight.push(right->right);
            leftAndRight.push(left->right);
            leftAndRight.push(right->left);
        }
        return true;
    }

572. 另一棵树的子树

bool compare(TreeNode* nodeLeft, TreeNode* nodeRight) {
        if (!nodeLeft && nodeRight)  return false;
        else if (nodeLeft && !nodeRight)  return false;
        // 没有左/右孩子节点时，当前递归返回true
        else if (!nodeLeft && !nodeRight)   return true;
        else if (nodeLeft->val != nodeRight->val)   return false;
        // 当前节点相等时，继续递归
        bool isSameOutside = compare(nodeLeft->left, nodeRight->left);
        bool isSameInside = compare(nodeLeft->right, nodeRight->right);
        return isSameOutside && isSameInside;
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root && !subRoot) return true;
        else if (!root && subRoot || root && !subRoot)   return false;
        else  return compare(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }

本题采用了双递归的方法，在《100.相同的树》的基础上，递归判断每个结点下的子树是否和目标子树相等。

这里没有采用KMP等算法，有兴趣的读者可以试一试。

111. 二叉树的最小深度

    int minDepth(TreeNode* root) {
        return GetDepth(root);
    }

    int GetDepth(TreeNode* node) {
        // 终止条件：节点为空时，该层深度为0
        if (!node)   return 0;
        int depthLeft = GetDepth(node->left);
        int depthRight = GetDepth(node->right);
        // 左空右不空，最小深度在右子树产生
        if (!node->left && node->right) {
            return 1 + depthRight;
        }
        // 右空左不空，最小深度在左子树产生
        if (node->left && !node->right) {
            return 1 + depthLeft;
        }
        // 左右都不空
        return 1 + min(depthLeft, depthRight);
    }

在递归逻辑设计阶段，要注意只有左右子树均为空的结点，才是最小深度层所在结点。

222. 完全二叉树的节点个数

int countNodes(TreeNode* root) {
        if (!root)  return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftHeight = 0, rightHeight = 0;
        // 左子树深度
        while (left) {
            left = left->left;
            leftHeight++;
        }
        // 右子树深度
        while (right) {
            right = right->right;
            rightHeight++;
        }
        // 如果是满二叉树
        if (leftHeight == rightHeight) {
            // 节点数量为2^h - 1;
            return (2 << leftHeight) - 1;
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }

本题利用完全二叉树的性质，递归时需要注意以下两点：

• 若为满二叉树，可以直接使用2^h-1进行计算。其中次方项利用位运算符'<<'实现；
• 若不是满二叉树，分别递归求解左右子树，左子树和右子树总能递归成一个满二叉树（一个单独的结点也是满二叉树）

110. 平衡二叉树

    bool isBalanced(TreeNode* root) {
        if (!root)   return true;
        int leftDepth = getHeight(root->left);
        int rightDepth = getHeight(root->right);
        if (abs(leftDepth - rightDepth) > 1) {
            return false;
        }
        else {
            return isBalanced(root->left) && isBalanced(root->right);
        }
    }

    int getHeight(TreeNode* node) {
        // 递归终止条件
        if (!node)   return 0;
        int leftDepth = getHeight(node->left);
        int rightDepth = getHeight(node->right);
        return max(leftDepth, rightDepth) + 1;
    }

类似572.另一棵树的子树，本题采用了双递归。求深度适合用前序遍历，而求高度适合用后序遍历。 

本题可以进行简化，在递归查找高度时就判断左右子树是否平衡：

    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }

    int getHeight(TreeNode* node) {
        // 递归终止条件
        if (!node)   return 0;
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1)    return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1)    return -1;
        // 查找高度时即可对是否平衡进行判断
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }