层序遍历 10

借助队列，从一层开始，遍历每一层的每个元素出队进结果，左右孩子都入队，遍历完队列里只剩下一层的节点，保存节点个数，再遍历这一层得到下一层，直到队列为空。

C++

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if (root == nullptr) return result;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            while (size--) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

C#

public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        List<IList<int>> result = new List<IList<int>>();
        Queue<TreeNode> que = new Queue<TreeNode>();
        if (root == null) return result;
        que.Enqueue(root);
        while (que.Count != 0) {
            int size = que.Count;
            List<int> vec = new List<int>();
            while(size-- > 0) {
                TreeNode cur = que.Dequeue();
                vec.Add(cur.val);
                if(cur.left != null) que.Enqueue(cur.left);
                if(cur.right != null) que.Enqueue(cur.right);
            }
            result.Add(vec);
        }
        return result;
    }
}

107层序遍历2

要求从最后一层向上从左到右输出，reverse一下就行了。

//C++
reverse(res.begin(), res.end());
//C#
result.Reverse(0, result.Count);

199二叉树的右视图

层序遍历的时候在每一层末节点记录值即可。

//C++
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> res;
        if (root == nullptr) return res;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* cur= que.front();
                if (size == 0) {
                    res.push_back(cur->val);
                }           
                que.pop();
                if (cur->left != nullptr) que.push(cur->left);
                if (cur->right != nullptr) que.push(cur->right);
            }
        }
        return res;
    }
};
//C#
public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        Queue<TreeNode> que = new Queue<TreeNode>();
        List<int> res = new List<int>();
        if (root == null) return res;
        que.Enqueue(root);
        while (que.Count != 0) {
            int size = que.Count;
            for (int i = 0; i < size; i++) {
                TreeNode cur = que.Dequeue();
                if (i == size - 1) res.Add(cur.val);
                if (cur.left != null) que.Enqueue(cur.left);
                if (cur.right != null) que.Enqueue(cur.right);
            }
        }
        return res;
    }
}

637二叉树的层平均值

写个sum记录下每层的平均值即可。

//C++
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        queue<TreeNode*> que;
        if (root == nullptr) return res;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            double cnt = size;
            long sum = 0;
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                sum += cur->val;
                if (cur->left != nullptr) que.push(cur->left);
                if (cur->right != nullptr) que.push(cur->right);
            }
            res.push_back(sum / cnt);
        }
        return res;
    }
};
//C#

public class Solution {
    public IList<double> AverageOfLevels(TreeNode root) {
        Queue<TreeNode> que = new Queue<TreeNode>();
        List<double> res = new List<double>();
        if (root == null) return res;
        que.Enqueue(root);
        while (que.Count != 0) {
            int size = que.Count;
            double sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode cur = que.Dequeue();
                sum += cur.val;
                if (cur.left != null) que.Enqueue(cur.left);
                if (cur.right != null) que.Enqueue(cur.right);
            }
            res.Add(sum / size);
        }
        return res;
    }
}

429 N叉树的层序遍历

遍历左右子树变成遍历所有子树即可。

//C++
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        queue<Node*> que;
        if (root == nullptr) return res;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            while (size--) {
                Node* cur = que.front();     
                que.pop();
                vec.push_back(cur->val);
                for (int i = 0; i < cur->children.size(); i++) {
                    if (cur->children[i] != nullptr) que.push(cur->children[i]);
                }
            }
            res.push_back(vec);
        }
        return res;
    }
};
//C#
public class Solution {
    public IList<IList<int>> LevelOrder(Node root) {
        Queue<Node> que = new Queue<Node>();
        IList<IList<int>> res = new List<IList<int>>();
        if (root == null) return res;
        que.Enqueue(root);
        while (que.Count != 0) {
            int size = que.Count;
            List<int> vec = new List<int>();
            for (int i = 0; i < size; i++) {
                Node cur = que.Dequeue();
                vec.Add(cur.val);
                for (int j = 0; j < cur.children.Count; j++) {
                    if (cur.children[j] != null) que.Enqueue(cur.children[j]);
                }
                
            }
            res.Add(vec);
        }
        return res;
    }
}

515. 在每个树行中找最大值

每一层记录最大值即可。

//C++
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> que;
        if (root == nullptr) return res;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            int max = INT_MIN;
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                if (cur->val > max) max = cur->val;
                if (cur->left != nullptr) que.push(cur->left);
                if (cur->right != nullptr) que.push(cur->right);
            }
            res.push_back(max);
        }
        return res;
    }
};
//C#
public class Solution {
    public IList<int> LargestValues(TreeNode root) {
        List<int> res = new List<int>();
        Queue<TreeNode> que = new Queue<TreeNode>();
        if (root == null) return res;
        que.Enqueue(root);
        while (que.Count != 0) {
            int size = que.Count;
            int max = int.MinValue;
            while (size-- > 0) {
                TreeNode cur = que.Dequeue();
                if (cur.val > max) max = cur.val;
                if (cur.left != null) que.Enqueue(cur.left);
                if (cur.right != null) que.Enqueue(cur.right);
            }
            res.Add(max);
        }
        return res;
    }
}

116.填充每个节点的下一个右侧节点指针

遍历的时候指一下指针就行了。

//C++
class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root == nullptr) return root;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                Node* node = que.front();
                que.pop();
                if (size == 0) {
                    node->next = nullptr;
                } else {
                    node->next = que.front();
                }
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};
//C#
public class Solution {
    public Node Connect(Node root) {
        Queue<Node> que = new Queue<Node>();
        if (root == null) return root;
        que.Enqueue(root);
        while (que.Count != 0) {
            int size = que.Count;
            while (size-- > 0) {
                Node cur = que.Dequeue();
                if (size == 0) {
                    cur.next = null;
                } else {
                    cur.next = que.Peek();
                }
                if (cur.left != null) que.Enqueue(cur.left);
                if (cur.right != null) que.Enqueue(cur.right);
            }
        }
        return root;
    }
}

117.填充每个节点的下一个右侧节点指针II

和上一题完全一样。

104. 二叉树的最大深度

层序遍历的时候记录层数即可。

//C++
class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if (root == nullptr) return 0;
        que.push(root);
        int depth = 0;
        while (!que.empty()) {
            int size = que.size();
            depth++;
            while (size--) {
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return depth;
    }
};
//C#
public class Solution {
    public int MaxDepth(TreeNode root) {
        Queue<TreeNode> que = new Queue<TreeNode>();
        if (root == null) return 0;
        que.Enqueue(root);
        int depth = 0;
        while (que.Count != 0) {
            int size = que.Count;
            depth++;
            while (size-- > 0) {
                TreeNode cur = que.Dequeue();
                if (cur.left != null) que.Enqueue(cur.left);
                if (cur.right != null) que.Enqueue(cur.right);
            }
            
        }
        return depth;
    }
}

111. 二叉树的最小深度

左右子树都为空时即达到最小深度。

//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:
    int minDepth(TreeNode* root) {
                queue<TreeNode*> que;
        if (root == nullptr) return 0;
        que.push(root);
        int depth = 0;
        while (!que.empty()) {
            int size = que.size();
            depth++;
            while (size--) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left == nullptr && node->right == nullptr) return depth;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return depth;
    }
};
//C#
public class Solution {
    public int MinDepth(TreeNode root) {
        Queue<TreeNode> que = new Queue<TreeNode>();
        if (root == null) return 0;
        que.Enqueue(root);
        int depth = 0;
        while (que.Count != 0) {
            int size = que.Count;
            depth++;
            while (size-- > 0) {
                TreeNode cur = que.Dequeue();
                if (cur.left == null && cur.right == null) return depth;
                if (cur.left != null) que.Enqueue(cur.left);
                if (cur.right != null) que.Enqueue(cur.right);
            }
            
        }
        return depth;
    }
}

226.翻转二叉树

递归

使用先序或者后序，中序会使第二次翻转反了，要两次左。

//C++
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};
//C#

public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        InvertTree(root.left);
        InvertTree(root.right);
        return root;
    }
}

二刷看一下迭代的非递归方法。

101.对称二叉树 2

递归三步走：

• 确定递归参数和返回值，即左子树节点和右子树节点，返回值是bool。
• 确定递归结束条件，左右子树有一个为空一个不为空，return false，都为空，return true，都不为空但不相等，return false，都不为空且相等，进入单层递归逻辑（如何使用下一层递归）。
• 递归单层逻辑：比较二叉树外侧是否对称（不是比数值，而是真个子树，相当于调用下一层递归逻辑）：传入的是左节点的左孩子，右节点的右孩子。 比较内测是否对称，传入左节点的右孩子，右节点的左孩子。 如果左右都对称就返回true ，有一侧不对称就返回false 。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        else return compare(root->left, root->right);
    }
    bool compare(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right != nullptr) return false;
        else if (left != nullptr && right == nullptr) return false;
        else if (left == nullptr && right == nullptr) return true;
        else if (left->val != right->val) return false;
        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        return outside && inside;
    }
};

二刷看看迭代法。

二刷

层序遍历模板

使用队列来维护元素动态变化的需求，其实栈和队列都是很好的动态容器，队列里放着当前层的元素，再自己遍历一遍就可以产生下一层的元素。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> que;
        //0.为空直接返回空数组
        if (root == nullptr) return res;
        //1.放入头结点
        que.push(root);
        while (!que.empty()) {
            //记录本层节点数量
            int size = que.size();
            vector<int> data;
            //遍历每个节点，添加其左右子节点
            for (int i = 0; i < size; i++) {
                TreeNode* temp = que.front();
                data.push_back(temp->val);
                if (temp->left) que.push(temp->left);
                if (temp->right) que.push(temp->right);
                que.pop();
            }
            res.push_back(data);
        }
        return res;
    }
};

层序遍历2

自底向上遍历，reverse一下数组。

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> que;
        if (root == nullptr) return res;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> data;
            for (int i = 0; i < size; i++) {
                TreeNode* temp = que.front();
                que.pop();
                data.push_back(temp->val);
                if (temp->left) que.push(temp->left);
                if (temp->right) que.push(temp->right);
            }
            res.push_back(data);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

二叉树的右视图

层序遍历的时候只收集最右边的节点。

    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> que;
        if (root == nullptr) return res;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* temp = que.front();
                que.pop();
                if (i == size - 1) res.push_back(temp->val);
                if (temp->left) que.push(temp->left);
                if (temp->right) que.push(temp->right);
            }
        }
        return res;
    }

二叉树的层平均值

层序遍历取一下每一层的平均值，double是双精度浮点，long是长整形。

    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        queue<TreeNode*> que;
        if (root == nullptr) return res;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            double sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode* temp = que.front();
                que.pop();
                sum += temp->val;
                if (temp->left) que.push(temp->left);
                if (temp->right) que.push(temp->right);
            }
            res.push_back(sum / size);
        }
        return res;
    }

在每个树层中找最大值

层序遍历记录每层最大值。

   vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> que;
        if (root == nullptr) return res;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            int max = INT_MIN;
            while (size--) {
                TreeNode* temp = que.front();
                que.pop();
                if (temp->val > max) max = temp->val;
                if (temp->left) que.push(temp->left);
                if (temp->right) que.push(temp->right);
            }
            res.push_back(max);
        }
        return res;
    }

N叉树的层序遍历

遍历每一层的时候，因为是N叉树，所以遍历子节点从左右变成所有children数组。

    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        vector<vector<int>> res;
        if (root == nullptr) return res;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> data;
            while (size--) {
                Node* temp = que.front();
                que.pop();
                data.push_back(temp->val);
                for (int i = 0; i < temp->children.size(); i++) {
                    if (temp->children[i]) que.push(temp->children[i]);
                }
            }
            res.push_back(data);
        }
        return res;
    }

填充每个节点的下一个右节点

每一层遍历的时候，前size - 1,指向next，最后一个置为nullptr。

    Node* connect(Node* root) {
        queue<Node*> que;
        if (root == nullptr) return nullptr;
      	que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                Node* temp = que.front();
                que.pop();
                if (i == size - 1) temp->next = nullptr;
                else temp->next = que.front();
                if (temp->left) que.push(temp->left);
                if (temp->right) que.push(temp->right);
            }
        }
        return root;
    }

填充每个节点的下一个右节点II

不要求是完美二叉树，同一层节点之间可以有空缺，和上一题一样。

二叉树的最大深度

每次while就是每一层。

    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        int cnt = 0;
        if (root == nullptr) return 0;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* temp = que.front();
                que.pop();
                if (temp->left) que.push(temp->left);
                if (temp->right) que.push(temp->right);
            }
            cnt++;
        }
        return cnt;
    }
	//DFS
    int max = INT_MIN;
    void doit(TreeNode* cur, int cnt) {
        if (cur == nullptr) return;
        cnt++;
        if (cnt > max) max = cnt;
        doit(cur->left, cnt);
        doit(cur->right, cnt);
    }
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        doit(root, 0);
        return max;
    }

二叉树的最小深度

当左右孩子都为空的时候，即遍历的最低点，对于层序那就是最低的，对于递归遍历那是有可能，要比较一下。

    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> que;
        int cnt = 0;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* temp = que.front();
                que.pop();
                if (temp->left == nullptr && temp->right == nullptr) return cnt + 1;
                if (temp->left) que.push(temp->left);
                if (temp->right) que.push(temp->right);
            }
            cnt++;
        }
        return cnt;
    }
	//DFS 
    int min = INT_MAX;
    void doit(TreeNode* cur, int cnt) {
        if (cur == nullptr) return;
        cnt++;
        if (cur->left == nullptr && cur->right == nullptr) min = cnt < min ? cnt : min;
        doit(cur->left, cnt);
        doit(cur->right, cnt);
    }
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        doit(root, 0);
        return min;
    }

翻转二叉树

递归遍历前序和后序都可以，中序的话不太行，因为从左子树翻转完，中在反转一次会变成右子树，再翻转的是之前的左子树。

    TreeNode* invertTree(TreeNode* root) {
        Doit(root);
        return root;
    }
    void Doit(TreeNode* cur) {
        if (cur == nullptr) return;
        TreeNode* temp = cur->left;
        cur->left = cur->right;
        cur->right = temp;
        Doit(cur->left);
        Doit(cur->right);
    }

层序遍历也OK。

    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root == nullptr) return root;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                TreeNode* temp = cur->left;
                cur->left = cur->right;
                cur->right = temp;

                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return root;
    }

迭代法，用栈存访问过的元素，指针来模拟迭代过程，前序。

    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root == nullptr) return root;
        TreeNode* cur = root;
        while (!st.empty() || cur != nullptr) {
            if (cur) {
                st.push(cur);
                TreeNode* temp = cur->left;
                cur->left = cur->right;
                cur->right = temp;
                cur = cur->left;
            }
            else {
                cur = st.top();
                st.pop();
                cur = cur->right;
            }
        }
        return root;
    }

对称二叉树

递归的第一部思考递归参数和返回值也很重要，当只传一个参数不太好解决的时候，考虑考虑传两个参数，尤其是针对树类型，另外if else有时候else是必须的有时候是可以不要的，如果几个if之间的变量彼此独立，就可以不写else，否则如果第一个if执会影响第二个if里的量那就要加else。

• 有一点要注意，这里点的对称指的是左右子树，而不是左右节点对称，是关于中轴线的对称。
• 实际先左后右递归是后序，左子树左右中，右子树右左中。

    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return root;
        return doit(root->left, root->right);
    }
    bool doit(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right == nullptr) return true;
        else if (left == nullptr && right != nullptr || left != nullptr && right == nullptr) return false;
        else if (left->val == right->val) {
            return doit(left->left, right->right) && doit(left->right, right->left);
        } else return false;
    }

迭代法使用队列，从root开始每次放一对left和right进队列，然后再弹出队首进行比较，注意这并不是层序遍历模板写法，但其实还是按每一层遍历的，由两边向中间搜索。

• 使用队列的时候注意都为空是continue继续检查下一层节点而不是直接return true，和递归不一样，递归返回的时候已经后续遍历完一遍数组了，递归是通过下层返回的结果反向向上推，而层序遍历是向下遍历的时候就得到了结果。

    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> que;
        if (root == nullptr) return true;
        que.push(root->left);
        que.push(root->right);
        while (!que.empty()) {
            TreeNode* left = que.front(); que.pop();
            TreeNode* right = que.front(); que.pop();
            if (left == nullptr && right == nullptr) continue;
            else if (left != nullptr && right == nullptr || left == nullptr && right != nullptr) return false;
            else if (left->val == right->val) {
                que.push(left->left);
                que.push(right->right);
                que.push(left->right);
                que.push(right->left);
            } else return false;
        }
        return true;
    }

实际上有个容器来存储遍历的元素就可以了，遍历顺序与容器无关，所以栈或者数组也可以完成，以栈为例，和队列的区别就在于出去的元素是从头还是尾出了。

• 栈由于先进后出的特性实际上是深度优先遍历，一条子树走到底，不过因为最后都会遍历完整棵树并且是对称问题，所以入栈是先左后右还是先右后左就无所谓了。

        stack<TreeNode*> que;
        if (root == nullptr) return true;
        que.push(root->right);
        que.push(root->left);
        while (!que.empty()) {
            TreeNode* left = que.top(); que.pop();
            TreeNode* right = que.top(); que.pop();
            if (left == nullptr && right == nullptr) continue;
            else if (left != nullptr && right == nullptr || left == nullptr && right != nullptr) return false;
            else if (left->val == right->val) {
                que.push(right->right);
                que.push(left->left);
                que.push(right->left);
                que.push(left->right);
            } else return false;
        }
        return true;
    }

• 三刷可视化看一下搜索过程 https://www.bilibili.com/video/BV1tz4y1M79Q。

相同的树 100

把比较的两棵树当两颗子树，只不过递归的时候左跟左比，右跟右比，而不是对称着比了，重点理解递归有两个参数的使用。5 min秒了，用递归写的。

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return Doit(p, q);
    }

    bool Doit(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        else if (p != nullptr && q == nullptr || p == nullptr && q != nullptr) return false;
        else if (p->val == q->val) {
            return Doit(p->left, q->left) && Doit(p->right, q->right);
        } else return false;
    }

};

另一颗的子树

套了两层递归，互相调用，三刷再看，是对称树的延伸