STAy's Blog

落叶的一生，只为了归根么？

【数据结构】树

发布于 2021-12-28 | 分类于 算法 、 数据结构 | 12分钟 | 2337字数

二叉树的前中后序遍历

前序遍历

前序遍历的访问和处理顺序是一致的，即先访问当前节点，再将该节点的左子树和右子树加入栈中。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
            // 先放右节点后放左节点，后进先出，所以出栈就是先左后右
        }
        return result;
    }
};

中序遍历

中序遍历的访问顺序和处理顺序是不一致的，即先访问该节点的左子树，返回来再访问该节点。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;
            }
            else {
                cur = st.top();
                st.pop();
                result.push_back(cur->val);
                cur = cur->right;
            }
        }
        return result;
    }
};

后序遍历

后序遍历是左右中，只需要将前序遍历的顺序变换一下就好了，前序遍历是先访问中，然后将右子树入栈、左子树入栈，最后的遍历的顺序就是中左右。

而现在可以先访问中，然后将左子树入栈、右子树入栈，那么访问顺序就是中右左，最后访问完后，将访问序列逆序过来就是左右中了。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
};

二叉树的层次遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                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;
    }
};

反转二叉树

https://leetcode-cn.com/problems/invert-binary-tree/

把每个节点的左右孩子调换顺序就行了，前序遍历和后序遍历都可以，但是中序遍历不行，因为中序遍历的特性会使有的节点的左右孩子调换两次。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        TreeNode *tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        if(root->left) invertTree(root->left);
        if(root->right)  invertTree(root->right);
        return root;
    }
};

对称二叉树※

https://leetcode-cn.com/problems/symmetric-tree/submissions/

这道题一开始我想的是直接层次遍历，看看每层的数值是不是“回文”，后来发现是“回文”是对称二叉树的必要不充分条件。

这道题需要比较根节点的两个子树的是不是对称的，对于左子树来说遍历顺序可以是左右中，那么对于右子树来说遍历顺序是右左中，其实不算是严格的后序遍历。

例如：

      1
     / \
    2   2
   / \ / \
  3  4 4  3
 / \     / \
5   6   6   5

左子树的左右中顺序遍历：56342

右子树的右左中顺序遍历：56342

所以可以用两个数组，分别将左右子树的按照刚才说的遍历顺序记录下来，然后对比是不是一样。

class Solution {
public:
    vector<int> left;
    vector<int> right;
    bool isSymmetric(TreeNode* root) {
        leftRightIn(root->left);
        rightLeftIn(root->right);
        if (left.size() != right.size()) {
            return false;
        }
        for (int i = 0; i < left.size(); i++ ){
            // cout << left[i] << " " << right[i] << endl;
            if (left[i] != right[i]) {
                return false;
            }
        }
        return true;
    }

    void leftRightIn(TreeNode* root) { // 左右中
        if (root == NULL) {
            left.push_back(-1);
            return ;
        }
        leftRightIn(root->left);
        leftRightIn(root->right);
        left.push_back(root->val);
    }

    void rightLeftIn(TreeNode* root) { // 右左中
        if (root == NULL) {
            right.push_back(-1);
            return ;
        }
        rightLeftIn(root->right);
        rightLeftIn(root->left);
        right.push_back(root->val);
    }

};

还有一种就是直接找到与该节点对称的节点，比较两个节点的值以及他们子树的值，就不用建立数组记录访问顺序了：

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   // 比较左子树的左子树和右子树的右子树
        bool inside = compare(left->right, right->left);    // 比较左子树的右子树和右子树的左子树
        bool isSame = outside && inside; 
        return isSame;

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

迭代法可以用队列，但是注意不是层次访问，每次将左->左、右->右、左->右，右->左加入队列，每次取出一对进行比较：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);   // 将左子树头结点加入队列
        que.push(root->right);  // 将右子树头结点加入队列
        
        while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};

由于队列每次只是存储每一层的节点，且每次从队列中取出的节点是一对，对与对之间的顺序不用严格控制，所以可以把队列直接替换成栈也行。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        stack<TreeNode*> st; // 这里改成了栈
        st.push(root->left);
        st.push(root->right);
        while (!st.empty()) {
            TreeNode* leftNode = st.top(); st.pop();
            TreeNode* rightNode = st.top(); st.pop();
            if (!leftNode && !rightNode) {
                continue;
            }
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            st.push(leftNode->left);
            st.push(rightNode->right);
            st.push(leftNode->right);
            st.push(rightNode->left);
        }
        return true;
    }
};

二叉树的最大深度

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

递归法很简单

class Solution {
public:
    int res = 0;
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        getdepth(root, 1);
        return res;
    }

    void getdepth(TreeNode* root, int k) {
        if (res < k) res = k;
        if (root->left) getdepth(root->left, k + 1);
        if (root->right) getdepth(root->right, k + 1);
    }

};

如果要是迭代法就是使用层次遍历，计算以下有多少层

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int res = 0;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            res ++;
            int len = q.size();
            for (int i = 0; i < len; i++ ) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return res;
    }
};

多叉树的深度

https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/

class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;
        int res = 0;
        queue<Node*> q;
        q.push(root);
        
        while (!q.empty()) {
            res ++;
            int len = q.size();
            for (int i = 0; i < len; i ++) {
                Node* node = q.front();
                q.pop();
                for (int j = 0; j < node->children.size(); j++ ) {
                    q.push(node->children[j]);
                }
            } 
        }
        return res;
    }
};

二叉树的最小深度

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

用层次遍历，当遇到左右孩子都为空的节点(叶子节点)时就返回，

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            res ++;
            int len = q.size();
            for (int i = 0; i < len; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (!node->left && !node->right) return res;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
        }
        return res;
    }
};

二叉树的所有路径

https://leetcode-cn.com/problems/binary-tree-paths/

这道题就是一道回溯题，递归的出口就是遇到叶子节点，麻烦的一点就是整数转字符串，C++不能直接转

class Solution {
public:
    vector<string> res;
    vector<string> binaryTreePaths(TreeNode* root) {
        string path = "";
        backtracking(root, path);
        return res;
    }

    void backtracking(TreeNode* root, string path) {
        if (!root->left && !root->right) {
            if (path != "") path += "->";
            path += intToString(root->val);
            res.push_back(path);
            return ;
        }
        
        if (path != "") path += "->"; 

        if (root->left) backtracking(root->left, path + intToString(root->val));
        if (root->right) backtracking(root->right, path + intToString(root->val));
    }

    string intToString(int x) {
        if (x == 0)  return "0";
        string str = "";
        bool negative = 0;
        if (x < 0) {
            negative = 1;
            x = -x;
        }
        while (x != 0) {
            string tmp = "";
            tmp += x % 10 + '0';
            str = tmp + str;
            x /= 10;
        }
        if (negative) 
        	return "-" + str;
        return str;
    }
};

平衡二叉树

https://leetcode-cn.com/problems/balanced-binary-tree/

要保证所有的节点都是平衡二叉树，所以每层递归都要返回该节点的高度，让上一层递归去判断左右子树的高度差。

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        return level(root) != -1;
    }

    int level(TreeNode* root) {
        if(!root) return 0;
        int left = level(root->left);
        if (left == -1) return -1;
        int right = level(root->right);
        if (right == -1) return -1;
        return abs(left - right) > 1 ? -1 : max(left, right) + 1;
    }
};
# 算法 # 数据结构
【算法】双指针 上一篇
【数据结构】链表 下一篇
0%