文章是为了记录hot100思路为了面试160.相交链表解题思路首先由题中已给信息可知链表A和链表B均不为空链表其次假设链表A和链表B的首个公共节点是node节点其中链表A中总的节点数是a链表B的节点总数是b从首个公共节点到链表结尾的节点数目是c。链表A的头节点headA链表B的头节点headB此处我们引入俩个指针指针A先遍历链表A再遍历链表B直到首个公共节点同理指针B先遍历链表B再遍历链表A直到首个公共节点。其中指针A走过的步数是a(b-c)其中指针B走过的步数是b(a-c)由上可知a(b-c)b(a-c)若c0则说明链表A链表B之间不存在公共节点此时指针A、B均指向null反之指针A、B同时指向第一个公共节点node。C/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *A headA; ListNode *B headB; while(A ! B) { A A ! nullptr ? A A-next : headB; B B ! nullptr ? B B - next : headA; } return A; } };python# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val x # self.next None class Solution(object): def getIntersectionNode(self, headA, headB): :type head1, head1: ListNode :rtype: ListNode A,B headA, headB while A! B: A A.next if A else headB B B.next if B else headA return A236.二叉树的最近公共祖先由题意可知若root是节点p、节点q的最近公共祖先那么应该是以下几种情况之一①节点p、节点q在root的左右子树当中②proot节点q在root的左右子树当中③qroot节点p在root的左右子树当中那么我们考虑使用递归来处理这个问题其中对于链表的遍历我们采用先序遍历。遇到节点p、节点q时返回当前的root由底至顶进行回溯当节点p/节点q位于root的左右子树中时节点root就是最近公共祖先则向上返回root。终止条件当root越过叶子节点直接返回null当root等于p/q直接返回root递归条件递归root的左子树返回值记为left递归root的右子树返回值记为right返回值根据left以及right的值进行判断有以下4种情况· leftNULL and rightnull说明root的左右子树当中都不存在p、q返回null· leftNULL and right !null说明root的左子树当中不存在节点p/q右子树当中存在节点p/q返回right· left!NULL and right null说明root的左子树当中存在节点p/q右子树当中不存在节点p/q返回left· left!NULL and right!null说明root的左右子树当中分别存在节点p/q返回rootC/** * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(rootNULL) return NULL; if(rootp || rootq) return root; TreeNode* leftlowestCommonAncestor(root-left, p,q); TreeNode* rightlowestCommonAncestor(root-right, p,q); if(leftNULLright!NULL) return right; if(left!NULLrightNULL) return left; if(leftNULLrightNULL) return NULL; return root; } };python# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val x # self.left None # self.right None class Solution(object): def lowestCommonAncestor(self, root, p, q): :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode if not root or rootp or rootq: return root left self.lowestCommonAncestor(root.left,p,q) right self.lowestCommonAncestor(root.right, p,q) if not left: return right if not right: return left return root参考引用资料具体的图解见Krahets大佬的文章。Krahets 160. 相交链表双指针清晰图解236. 二叉树的最近公共祖先DFS 清晰图解
Leetcode HOT 100
文章是为了记录hot100思路为了面试160.相交链表解题思路首先由题中已给信息可知链表A和链表B均不为空链表其次假设链表A和链表B的首个公共节点是node节点其中链表A中总的节点数是a链表B的节点总数是b从首个公共节点到链表结尾的节点数目是c。链表A的头节点headA链表B的头节点headB此处我们引入俩个指针指针A先遍历链表A再遍历链表B直到首个公共节点同理指针B先遍历链表B再遍历链表A直到首个公共节点。其中指针A走过的步数是a(b-c)其中指针B走过的步数是b(a-c)由上可知a(b-c)b(a-c)若c0则说明链表A链表B之间不存在公共节点此时指针A、B均指向null反之指针A、B同时指向第一个公共节点node。C/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *A headA; ListNode *B headB; while(A ! B) { A A ! nullptr ? A A-next : headB; B B ! nullptr ? B B - next : headA; } return A; } };python# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val x # self.next None class Solution(object): def getIntersectionNode(self, headA, headB): :type head1, head1: ListNode :rtype: ListNode A,B headA, headB while A! B: A A.next if A else headB B B.next if B else headA return A236.二叉树的最近公共祖先由题意可知若root是节点p、节点q的最近公共祖先那么应该是以下几种情况之一①节点p、节点q在root的左右子树当中②proot节点q在root的左右子树当中③qroot节点p在root的左右子树当中那么我们考虑使用递归来处理这个问题其中对于链表的遍历我们采用先序遍历。遇到节点p、节点q时返回当前的root由底至顶进行回溯当节点p/节点q位于root的左右子树中时节点root就是最近公共祖先则向上返回root。终止条件当root越过叶子节点直接返回null当root等于p/q直接返回root递归条件递归root的左子树返回值记为left递归root的右子树返回值记为right返回值根据left以及right的值进行判断有以下4种情况· leftNULL and rightnull说明root的左右子树当中都不存在p、q返回null· leftNULL and right !null说明root的左子树当中不存在节点p/q右子树当中存在节点p/q返回right· left!NULL and right null说明root的左子树当中存在节点p/q右子树当中不存在节点p/q返回left· left!NULL and right!null说明root的左右子树当中分别存在节点p/q返回rootC/** * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(rootNULL) return NULL; if(rootp || rootq) return root; TreeNode* leftlowestCommonAncestor(root-left, p,q); TreeNode* rightlowestCommonAncestor(root-right, p,q); if(leftNULLright!NULL) return right; if(left!NULLrightNULL) return left; if(leftNULLrightNULL) return NULL; return root; } };python# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val x # self.left None # self.right None class Solution(object): def lowestCommonAncestor(self, root, p, q): :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode if not root or rootp or rootq: return root left self.lowestCommonAncestor(root.left,p,q) right self.lowestCommonAncestor(root.right, p,q) if not left: return right if not right: return left return root参考引用资料具体的图解见Krahets大佬的文章。Krahets 160. 相交链表双指针清晰图解236. 二叉树的最近公共祖先DFS 清晰图解
