门户网站的主要特点,苏州市建设工程质量监督站网站,插画原画十大培训机构,wordpress有点尴尬诶该页无法显示236.二叉树的公共祖先
思路
看到题想的是找到两个点的各自路径利用stack保存#xff0c;根据路径长度大小将两个stack的值对齐到同一层#xff0c;之后同时出栈节点#xff0c;若相同则找到祖先节点。但是效率不高
看了大佬代码#xff0c;递归思想很难理解。
根据大佬…236.二叉树的公共祖先
思路
看到题想的是找到两个点的各自路径利用stack保存根据路径长度大小将两个stack的值对齐到同一层之后同时出栈节点若相同则找到祖先节点。但是效率不高
看了大佬代码递归思想很难理解。
根据大佬代码思想写了一个便于理解的版本分为四种情况递归求解。
代码
简单方法 StackTreeNode stacknew Stack();public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {int deep_pfindDeep(root,p,1);StackTreeNode stack_pnew Stack();stack_p.addAll(stack);stack.clear();int deep_qfindDeep(root,q,1);StackTreeNode stack_qnew Stack();stack_qstack;//将p作为长端if (deep_pdeep_q){int temp;StackTreeNode stack1new Stack();tempdeep_q;stack1.addAll(stack_q);stack_q.clear();deep_qdeep_p;stack_q.addAll(stack_p);stack_p.clear();deep_ptemp;stack_p.addAll(stack1);}while (deep_pdeep_q){stack_p.pop();deep_p--;}TreeNode node_qstack_q.pop(),node_pstack_p.pop();while (node_q!node_p){node_qstack_q.pop();node_pstack_p.pop();}return node_q;}public int findDeep(TreeNode root,TreeNode node,int deep){stack.push(root);if (rootnull) return 0;if (rootnode) return deep;int leftfindDeep(root.left,node,deep1);if (left0) stack.pop();int rightfindDeep(root.right,node,deep1);if (right0) stack.pop();return Math.max(left,right);}
大佬代码比较难懂On
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null || root p || root q) return root;TreeNode left lowestCommonAncestor(root.left, p, q);TreeNode right lowestCommonAncestor(root.right, p, q);if(left null) return right;if(right null) return left;return root;}
}
思想简化代码O(4*n),多了4次find
public class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (rootnull) return null;if (proot || qroot) return root;//第一种情况p,q其中一个为祖先节点if (find(root.left,p) find(root.left,q)){ //第二种情况p,q在当前节点左侧return lowestCommonAncestor(root.left,p,q);}if (find(root.right,p) find(root.right,q)){//第三种情况p,q在当前节点右侧return lowestCommonAncestor(root.right,p,q);}//第四种情况p,q在两边return root;}public boolean find(TreeNode root,TreeNode p){if (rootnull) return false;if (rootp) return true;return find(root.left,p) || find(root.right,p);}}
