111(求最低深度)
思路:找出左右子树是否是最小,注意会出现没有左右子树的现象
226(反转二叉树)
思路:递归遍历,然后交换
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root==NULL) return 0; invertTree(root->left); invertTree(root->right); swap(root->left,root->right); return root; } };
100(判断相同的树)
思路:先判断父节点是否相同,然后再分别递归判断左右叶子节点是否相同。注意当有任一父节点为空的时候,结果都为false。
101(对称二叉树判断)
思路:深搜左右子节点是否满足:左边的左节点=右边的右节点,右边的左节点=左边的右节点
222
110
112:(是否存在左右节点相加的和等于目标值的路径)
思路:分别递归搜索左右子树的和是否等于一条连续的叶子节点
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if(root==NULL) return 0; if(root->left==NULL&&root->right==NULL) return root->val==sum; if(hasPathSum(root->left,sum-root->val)) return true; if(hasPathSum(root->right,sum-root->val)) return true; return false; } };
404
257(找出二叉树所有路径)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> res; if(root==NULL) return res; if(root->left==NULL&&root->right==NULL){ res.push_back(to_string(root->val)); return res; } vector<string> leftS=binaryTreePaths(root->left); for (int i=0;i<leftS.size();i++) res.push_back(to_string(root->val) + "->" + leftS[i]); vector<string> rightS=binaryTreePaths(root->right); for (int i=0;i<rightS.size();i++) res.push_back(to_string(root->val)+"->"+rightS[i]); return res; } };
113
129
437