236. Lowest Common Ancestor of a Binary Tree
问题描述: Given a binary tree,find the lowest common ancestor (LCA) of two given nodes in the tree. According to the?definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p?and q?as the lowest node in T that has both p?and q?as descendants (where we allow?a node to be a descendant of itself).” Given the following binary tree:? root =?[3,5,1,6,2,8,null,7,4] _______3______ / ___5__ ___1__ / / 6 _2 0 8 / 7 4 Example 1: Input: root = [3,4],p = 5,q = 1 Output: 3 Explanation: The LCA of of nodes and is 513. Example 2: Input: root = [3,q = 4 Output: 5 Explanation: The LCA of nodes and is,since a node can be a descendant of itself according to the LCA definition.545 Note:
? 解题思路: 找两个节点最低的祖先节点,并且一个节点可以成为它自己的祖先节点。 我们可以先找到其中一个节点,这个时候我们需要遍历树,我在这里采用的是使用栈的前序遍历,当该节点值等于目标节点其中一个的值时,跳出循环。 找到的点为findN,未找到的为targetN 这个时候我们可以考虑两个点之间的关系: 1. targetN是findN的子节点 2.targetN不是findN的子节点 所以我们首先需要搜寻findN的子树,若包含targetN,则直接返回findN 若不包含,则需要从栈内弹出一个节点并且搜寻它的子树。 这里我们可以进行剪枝,因为此时栈顶是我们findN的父节点,并且我们已经搜索过了findN的子树,我们就不需要搜索它的左子树了。 但是targetN很可能是findN的父节点, 所以我们先要对栈顶值进行检查,如果不是我们想要找的值,则检查它的右子树 ? 代码: /** * 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) { stack<TreeNode*> stk; int restNode = 2; TreeNode* cur = root; while(cur || !stk.empty()){ if(cur){ if(cur->val == p->val || cur->val == q->val){ break; } stk.push(cur); cur = cur->left; }else{ cur = stk.top(); stk.pop(); cur = cur->right; } } TreeNode* targetN = cur->val == p->val ? q : p; TreeNode* findN = cur; if(containsNode(cur,targetN)){ return cur; } while(!stk.empty()){ cur = stk.top(); if(cur->val == targetN->val) break; stk.pop(); if(containsNode(cur->right,targetN)) break; } return cur; } bool containsNode(TreeNode* root,TreeNode* t){ if(!root) return false; stack<TreeNode*> stk; TreeNode* cur = root; while(cur || !stk.empty()){ if(cur){ if(cur->val == t->val) return true; stk.push(cur); cur = cur->left; }else{ cur = stk.top(); stk.pop(); cur = cur->right; } } return false; } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |