題目：求一棵二叉樹中兩個節(jié)點的最低公共父節(jié)點

思路：遞歸 和 非遞歸

public static TreeNode getLastCommonParentRec(TreeNode root, TreeNode node1, TreeNode node2) {if (found(root.left, node1)) {if (found(root.right, node2)) {return root;} else {return getLastCommonParentRec(root.left, node1, node2);}} else {if (found(root.left, node2)) {return root;} else {return getLastCommonParentRec(root.right, node1, node2);}}}public static boolean found(TreeNode root, TreeNode node) {if (root == null || node == null)return false;if (root == node)return true;boolean found = found(root.left, node);if (!found) {found = found(root.right, node);}return found;}

簡潔版遞歸：

public static TreeNode getLastCommonParentRec2(TreeNode root, TreeNode node1, TreeNode node2) {if (root == null)return null;if (root.equals(node1) || root.equals(node2)) {return root;}TreeNode left = getLastCommonParentRec2(root.left, node1, node2);TreeNode right = getLastCommonParentRec2(root.right, node1, node2);if (left != null && right != null) {return root;}if (left != null)return left;return right;}

?

轉(zhuǎn)載于:https://www.cnblogs.com/lfdingye/p/7372541.html

總結(jié)

以上是生活随笔為你收集整理的求一颗二叉树中两个节点的最低公共父节点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。