Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to find the nearest common ancestor of binary tree by Java". Friends who are interested might as well take a look. The method introduced in this paper is simple, fast and practical. Let the editor take you to learn "how to find the nearest common ancestor of a binary tree by Java".

Idea 1: assume that the tree is a binary search tree

First of all, let's add what a binary search tree is:

In the binary search tree, for each node, the value in his left subtree is smaller than him, and the value in the right subtree is larger than him. So the middle order traversal of the binary search tree is an ordered set of data.

For the above tree, assume that the nearest common ancestor of p Q is required.

Then it has the following situations:

For an ordinary binary tree, there are only a few cases: pq is on the left, pq is on the right, pq is left and right, and pq has a root node.

So recursively go to the left subtree and the right subtree to find the common ancestor of the p Q node, and return the node if it is found, and empty if it is not found.

According to the above ideas, it is easy to write code.

Public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode Q) {if (root = = null) return null; / / p is the root node of the current tree if (p = = root) return p; / / Q is the root node of the current tree if (Q = root) return Q; / / go to the left subtree to find TreeNode left = lowestCommonAncestor (root.left,p,q); / / go to the right subtree to find TreeNode right = lowestCommonAncestor (root.right,p,q) / / if (left! = null & & right! = null) {return root;} / / found on the left, no if (left! = null) {return left;} if (right! = null) {return right;} return null;} idea 2: suppose the tree is represented by the parents of the child.

Each node keeps the address of its parent node, which can be found on the Internet until the first intersection of the two linked lists is found, which is their common ancestor.

For the ordinary binary tree, it can only be found layer by layer, not up, so it is necessary to keep the path of two nodes until the last same node of the two paths. Here we use the stack to keep the paths of the two nodes.

The elements in the stack with many elements are popped first, and then the two stacks are popped together until the nodes to be popped are equal, which is their nearest common ancestor.

So the biggest difficulty here is the storage path.

Here, the stack is used to store the path. When traversing to a node, the node is placed on the stack, and then the left and right trees of the node are recursively searched. If found, the path is reserved, and if it is not found, it pops up.

Suppose you look for the p of the following figure:

First put the root node on the stack, recursively find the left subtree of the root node, pop up if you can't find it, and find it in the right subtree.

When root walks to 6, it is found that the left and right sides of the node are empty, indicating that the target node has not been found in the subtree. Pop up 6 and continue to search in the right subtree of 5.

Similarly, it can not be found in the right subtree of 5, it will pop up until you go to the right subtree of 3, come to 1, and find it.

/ / path used to find the node public boolean getPath (TreeNode root, TreeNode node, Stack stack) {if (root = = null | | node = = null) {return false;} / / put the current node on the stack stack.push (root); if (root.val = = node.val) {return true / / found} / / the current node is not found, go to the left subtree to find boolean flag = getPath (root.left,node,stack); / / find it in the left subtree, directly return if (flag) {return true;} / / the left subtree is not found, go to the right subtree to find flag = getPath (root.right,node,stack) / / found in the right subtree, directly returned if (flag) {return true;} / / none of the left and right subtrees were found, pop-up node stack.pop (); return false;} public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode Q) {if (root = = null) {return null;} Stack stackp = new Stack (); Stack stackq = new Stack () / / get the path getPath (root,p,stackp) of p Q; getPath (root,q,stackq); int sizep = stackp.size (); int sizeq = stackq.size (); if (sizep > sizeq) {int size = sizep-sizeq; / / until the number of elements in the two stacks is equal while (size > 0) {stackp.pop () Size--;}} else {int size = sizeq-sizep; / / eject elements until the number of elements in the two stacks is equal while (size > 0) {stackq.pop (); size-- }} / / pop up together until the first identical element while (! stackp.isEmpty () & &! stackq.isEmpty ()) {if (stackp.peek () = = stackq.peek ()) {/ / is found, the node return stackq.pop ();} else {stackp.pop () is returned Stackq.pop ();}} / / not found, return null return null;} so far, I believe you have a better understanding of "how to find the nearest common ancestor of a binary tree by Java". You might as well do it in practice! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.