自底向上遍历树避免重复计算

其实就是post-order traversal

有2道题可以用到这个技巧

1 Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

 

2

判断二叉树是不是平衡

http://zhedahht.blog.163.com/blog/static/25411174201142733927831/

http://www.geeksforgeeks.org/check-given-binary-tree-follows-height-property-red-black-tree/

 

3.

http://leetcode.com/2010/11/largest-binary-search-tree-bst-in.html

Naive Approach:
A naive approach is to reuse the solution from Determine if a Binary Tree is a Binary Search Tree. Starting from the root, we process in the order of current node, left child, then right child. For each node, you would call isBST() to check if the current subtree is a BST. If it is, then we have found the largest BST subtree. If it is not, then we have to continue examining its left and right child. If only one of the subtrees is BST, then we can return that subtree. However, if both left and right subtrees are BSTs, then we have to compare which subtree is larger (has more descendant nodes), then return the larger one.

Assume that we have a complete tree (ie, all leaves are at the same depth) with n nodes, the naive approach’s run time complexity is O(n lg n). The proof is left as an exercise to the reade

A Bottom-up Approach:
The naive approach is using a top-down approach. It is hardly efficient, simply because we are calling isBST() over and over again. Each time isBST() is called, it traverses down to the leaves to verify if the subtree is a BST.

Advertisements

One thought on “自底向上遍历树避免重复计算

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s