力扣刷题笔记——二叉树

首先定义二叉树节点的结构体

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

上手一道二叉树的翻转：

很明显，（🐂）需要使用递归来完成这道题目，递归不好理解，但下面的方案还是很好理解的，这道题有两种方式，从上到下（❀就是从根节点到叶子节点），或者是从下到上（同理可得）

那么我们开始分析：要反转树，两个方式（交换值或者交换节点指针），交换值就是书的结构不变，改变节点处的值，节点就是改变节点的指向的位置，原理一样，大家都用节点，开用

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

很简单一看就懂，先交换左右子树，然后依次交换左右子树的左右子树，反反复复，over

从下到上的意思，你左右子树都交换过了，那么直接交换左右子树不就行了。

上代码：

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

比第一种解法少了一行，但是理解没有第一个快。