数据结构与算法再探（二）树

二叉树

二叉树遍历

C++ 递归

C++迭代

python递归

层次遍历

二叉树的最大深度及直径

python 版递归树深度

递归求宽度

反转二叉树

python递归实现

代码可视化

二叉树

二叉树遍历

C++ 递归

通过调用自身来解决问题，将原问题分解为一个或多个规模较小的相似子问题，在函数体内调用自身来解决问题。递归算法需要定义基本情况（边界条件），以防止无限递归。

class Solution {
public:
    void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val); #先根
        preorder(root->left, res);
        // res.push_back(root->val); #中
        preorder(root->right, res);
        //res.push_back(root->val); #后
    }
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};

C++迭代

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        stack<TreeNode*> stk;
        stk.push(root);
        while (stk.size()) {
            auto node = stk.top();
            stk.pop();
            res.push_back(node->val);
            if (node->right) {
                stk.push(node->right);
            }
            if (node->left) {
                stk.push(node->left);
            }
        }
        return res;
    }
};

python递归

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if not root:
                return
            res.append(root.val) #改变位置进行先、中、后、遍历
            dfs(root.left)
            dfs(root.right)
        res=[]
        dfs(root)
        return res

层次遍历

637. 二叉树的层平均值 - 力扣（LeetCode）

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

二叉树的最大深度及直径

python 版递归树深度

递归虽然简洁但是有时难以写出和理解，每一次的递归调用都是一次完成函数的调用，需要梳理在递归临界点返，和返回后函数继续执行后最后，还要梳理回到上一次的递归调用节点间继续调用，着实难以理解，但是递归很多适用于树的操作。

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        ld=self.maxDepth(root.left)
        rd=self.maxDepth(root.right)
        return max(ld,rd)+1
#递归子问题返回结果给上一级，不能陷入直观上的顺序执行，return max(ld,rd)+1却决于左右子树是否
#有节点，这个返回值第一次返回时也许经历了很多次的函数压栈，多次调用

递归求宽度

543. 二叉树的直径

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.res=0
        def dfs(root):
            if not root: return 0
            ld=dfs(root.left)
            rd=dfs(root.right)
            self.res=max(self.res,ld+rd)
            return max(ld,rd)+1
        dfs(root)
        return self.res

反转二叉树

翻转二叉树

python递归实现

class Solution:
    def flipTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:return
        temp=root.left
        root.left, root.right=self.flipTree(root.right),self.flipTree(temp)
        return root