Day15 | 二叉树的层序遍历 对称

102. 二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    qu := make([]*TreeNode, 0)
    res := make([][]int, 0)
    qu = append(qu, root)
    for len(qu) != 0 {
        size := len(qu)
        list := make([]int, 0)
        for i := 0; i < size; i ++ {
            top := qu[0]
            qu = qu[1:]
            list = append(list, top.Val)
            if top.Left != nil {
                qu = append(qu, top.Left)
            }
            if top.Right != nil {
                qu = append(qu, top.Right)
            }
        }
        res = append(res, list)
    }
    return res
}

C++实现

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        // 思路：使用队列，一层一层的加入
        if(root == nullptr) return {};
        vector<vector<int>> res;
        queue<TreeNode *> qu;
        qu.push(root);
        while(!qu.empty()) {
            // 接受每一层的结点
            vector<int> level;
            int size = qu.size();
            // 这里的循环条件是队列长度，表示这一层的节点个数
            while(size --) {
                auto tmp = qu.front();
                qu.pop();
                level.push_back(tmp->val);
                if(tmp->left) qu.push(tmp->left);
                if(tmp->right) qu.push(tmp->right);
            }
            res.push_back(level);
        }
        return res;
    }
};

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

C++实现

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return nullptr;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    // 思路：左节点的左边等于右节点的右边，左节点的右边等于右节点的左边
    if root == nil {
        return true
    }
    
    return help(root.Left, root.Right)
}

func help(left, right *TreeNode) bool {
    if left == nil && right == nil {
        return true
    }
    if left == nil || right == nil {
        return false
    }
    if left.Val != right.Val {
        return false
    }
    return help(left.Left, right.Right) && help(left.Right, right.Left)
}

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        // 特殊情况
        if(root == nullptr) return root;
        return isSym(root->left, root->right);
    }
    bool isSym(TreeNode* left, TreeNode * right) {
        // 递归结束的条件
        if(left == nullptr && right == nullptr) return true;
        if(left == nullptr || right == nullptr) return false;
        if(left->val != right->val) return false;
        return isSym(left->left, right->right) && isSym(left->right, right->left);
    }
};