二叉树的最大深度
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int maxDepth(struct TreeNode* root){if(root){int l, r;l = maxDepth(root->left);r = maxDepth(root->right);if(l > r)return l + 1;else return r + 1;}else return 0;}
class Solution {public int maxDepth(TreeNode root) {return trans(root);}private int trans(TreeNode root){int l, r;if(root == null)return 0;l = trans(root.left);r = trans(root.right);int max = (l > r) ? l : r;return max + 1;}}
对称二叉树
https://leetcode-cn.com/problems/symmetric-tree/submissions/
bool check(struct TreeNode* a, struct TreeNode* b){if(a == NULL && b == NULL)return true;else if(a == NULL || b == NULL)return false;else if(a->val != b->val)return false;return check(a->left, b->right) && check(a->right, b->left);}bool isSymmetric(struct TreeNode* root){return check(root->left, root->right);}
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null)
return true;
return compare(root.left, root.right);
}
public boolean compare(TreeNode a, TreeNode b){
if(a == null && b == null){
return true;
}
else if(a == null || b == null){
return false;
}
else if(a.val != b.val){
return false;
}
else{
return (compare(a.left, b.right) && compare(a.right, b.left));
}
}
}
路径总和
https://leetcode-cn.com/problems/path-sum/
bool hasPathSum(struct TreeNode* root, int targetSum){
if(root == NULL)
return false;
if(root->left == NULL && root->right == NULL && targetSum == root->val)
return true;
return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
if(root.left == null && root.right == null)
return root.val == targetSum;
else return a(root, targetSum);
}
public boolean a(TreeNode root, int targetSum){
if(targetSum == 0 && root.left == null && root.right == null){
return true;
}
else if(root == null)
return false;
else return (hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val));
}
}
从前序与中序遍历序列构造二叉树
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
if(preorderSize == 0)
return NULL;
else{
int p = 0;
while(*(inorder + p) != *preorder)
p++;
//p为中序遍历分割下标
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
//node为父节点
node->val = *preorder;
node->left = buildTree(preorder + 1, p, inorder, p); //左子树
node->right = buildTree(preorder + p + 1, preorderSize - 1 - p, inorder + p + 1, preorderSize - 1 - p);
return node;
}
}
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
public TreeNode build(int[] preorder, int[] inorder, int pLeft, int pRight, int iLeft, int iRight){
if(pLeft > pRight)
return null;
TreeNode root = new TreeNode(preorder[pLeft]);
int i;
for(i = iLeft; inorder[i] != preorder[pLeft]; i++){}
//i为root在inorder中对应的下标
int leftCount = i - iLeft; //左子树元素个数
root.left = build(preorder, inorder, pLeft + 1, pLeft + leftCount, iLeft, leftCount + iLeft - 1);
root.right = build(preorder, inorder, pLeft + leftCount + 1, pRight, leftCount + iLeft + 1, iRight);
return root;
}
}
从中序与后序遍历序列构造二叉树
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
}
public TreeNode build(int[] inorder, int[] postorder, int iLeft, int iRight, int pLeft, int pRight){
if(iLeft > iRight)
return null;
TreeNode root = new TreeNode(postorder[pRight]);
int i;
for(i = iLeft; postorder[pRight] != inorder[i]; i++){}
int rightCount = iRight - i;
root.right = build(inorder, postorder, i + 1, iRight, pRight - rightCount, pRight - 1);
root.left = build(inorder, postorder, iLeft, i - 1, pLeft, pRight - rightCount - 1);
return root;
}
}
填充每个节点的下一个右侧节点指针（完美二叉树）
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
class Solution {
public Node connect(Node root) {
if(root == null)
return null;
Node left = root;
//left为每行最左边节点
while(left.left != null){
//下一层还有节点
Node cur = left;
while(true){
cur.left.next = cur.right;
if(cur.next == null)
//右侧没有节点，退出循环
break;
cur.right.next = cur.next.left;
cur = cur.next;
}
left = left.left;
//移动到下一层
}
return root;
}
}
填充每个节点的下一个右侧节点指针（任意二叉树）
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
class Solution {
public Node connect(Node root) {
if(root == null)
return null;
Node left = root;
while(left.left != null || left.right != null || left.next != null){
boolean flag = true;
Node cur = left;
while(true){
if(cur.left != null){
cur.left.next = find(cur, true);
flag = false;
}
if(cur.right != null){
cur.right.next = find(cur, false);
flag = false;
}
if(cur.next == null)
break;
if(flag && cur.next != null)
left = left.next;
cur = cur.next;
}
if(left.left != null)
left = left.left;
else if(left.right != null)
left = left.right;
}
return root;
}
public Node find(Node node, boolean left){
if(left){
if(node.right != null)
return node.right;
while(node.next != null){
node = node.next;
if(node.left != null)
return node.left;
if(node.right != null)
return node.right;
}
}
else{
while(node.next != null){
node = node.next;
if(node.left != null)
return node.left;
if(node.right != null)
return node.right;
}
}
return null;
}
}
二叉树的最近公共祖先
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
class Solution {
TreeNode result = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
find(root, p, q);
return result;
}
public boolean find(TreeNode root, TreeNode p, TreeNode q){
if(root == null)
return false;
boolean l = result == null && find(root.left, p, q);
boolean r = result == null && find(root.right, p, q);
if((l && r) || ((root.val == p.val || root.val == q.val) && (l || r))){
result = root;
return false;
}
return root.val == p.val || root.val == q.val || l || r;
}
}
若有收获，就点个赞吧
0 人点赞
