本文主要是介绍Tree的Traverse and divided conquer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Tree的traverse，Preorder, Inorder, Postorder ，这些都是用stack来模拟考察的比较多。参考这里： PreOrder, InOrder, PostOrder 题型总结
这里主要总结，divide and conquer 逻辑，往上返回result的情况；
Lowest Common Ancestor of a Binary Search Tree 思路：这题跟 Lowest Common Ancestor of Binary Tree 一模一样。思路：就是找p的节点在不在左支，或者右支，找到各自左右节点，然后进行比较，如果两者不一样，说明当前的root就是lowest 父节点，如果左边为空，那就都在右边，返回右边的即可，如果右边为空，那就都在左边，返回左边的即可。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q) {return root;}if(root.val < p.val && root.val < q.val) {return lowestCommonAncestor(root.right, p, q);} else if(root.val > p.val && root.val > q.val) {return lowestCommonAncestor(root.left, p, q);} else {return root;}}
}Lowest Common Ancestor of a Binary Tree (BT，就是两边返回，然后判断哪个为null，如果是null，返回另外一个，两个都不是null，返回当前);
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q) {return root;}TreeNode leftnode = lowestCommonAncestor(root.left, p, q);TreeNode rightnode = lowestCommonAncestor(root.right, p, q);if(leftnode == null) {return rightnode;} else if(rightnode == null) {return leftnode;} else {// leftnode != null && rightnode != null;return root;}}
}
这篇关于Tree的Traverse and divided conquer的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
