GVKun编程网logo

Diameter of Binary Tree

15

在本文中，我们将带你了解DiameterofBinaryTree在这篇文章中，同时我们还将给您一些技巧，以帮助您实现更有效的173.BinarySearchTreeIterator-Medium、33

在本文中，我们将带你了解Diameter of Binary Tree在这篇文章中，同时我们还将给您一些技巧，以帮助您实现更有效的173. Binary Search Tree Iterator - Medium、331. Verify Preorder Serialization of a Binary Tree、543. Diameter of Binary Tree、543.Diameter of Binary Tree。

本文目录一览：

Diameter of Binary Tree

Diameter of Binary Tree

Given a binary tree,you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree 

          1
         /         2   3
       / \     
      4   5

 

Return 3,which is the length of the path [4,2,1,3] or [5,3].

Note: The length of path between two nodes is represented by the number of edges between them.

 1 /**
 2  * DeFinition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class Solution {
11     public int diameterOfBinaryTree(TreeNode root) {
12         int[] globalMax = new int[1];
13         helper(root,globalMax);
14         return globalMax[0] - 1 <= 0 ? 0 : globalMax[0] - 1;
15     }
16     
17     private int helper(TreeNode root,int[] globalMax) {
18         if (root == null) return 0;
19         int leftMaxWithRoot = helper(root.left,globalMax);
20         int leftRightWithRoot = helper(root.right,globalMax);
21         
22         int maxWithRoot = Math.max(leftMaxWithRoot,leftRightWithRoot) + 1;
23         globalMax[0] = Math.max(globalMax[0],leftMaxWithRoot + leftRightWithRoot + 1);
24         return maxWithRoot;
25     }
26 }

173. Binary Search Tree Iterator - Medium

173. Binary Search Tree Iterator - Medium

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

 

Example:

分享图片

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

 

Note:

  • next() and hasNext() should run in average O(1) time and uses O(h) memory,where h is the height of the tree.
  • You may assume that next() call will always be valid,that is,there will be at least a next smallest number in the BST when next() is called.

 

M1: 先inorder全部遍历完（慢）

time: O(n), space: O(n)

/**
 * DeFinition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {
    List<Integer> list;
    int idx;

    public BSTIterator(TreeNode root) {
        list = new ArrayList<>();
        idx = 0;
        inorder(root,list);
    }
    
    public void inorder(TreeNode root,List<Integer> list) {
        if(root == null) {
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
    
    /** @return the next smallest number */
    public int next() {
        int tmp = idx;
        idx++;
        return list.get(tmp);
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return idx < list.size();
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

 

M2: optimized，用stack，先把所有的左边的节点压进栈，当call next()时再按顺序出栈

next()　　　   -- time: O(h),space: O(h)

hasNext()　　-- time: O(1)

/**
 * DeFinition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {
    Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {
        getAllLeft(root);
    }
    
    public void getAllLeft(TreeNode root) {
        while(root != null) {
            stack.push(root);
            root = root.left;
        }
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        getAllLeft(node.right);       
        return node.val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

331. Verify Preorder Serialization of a Binary Tree

331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

_9_ / \ 3 2 / \ / \ 4 1 # 6 / \ / \ / \ # # # # # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false


我的解答：  代码太长

class Solution {
    • public:
    • bool isValidSerialization(string preorder) {
    • int len = preorder.size();
  • int count = 0;
  • if(len == 1 && preorder[0]=='#')
  • return true;
  • string s = "";
  • vector<string> res;
  • for(int i = 0; i < len; i++){
  • if(preorder[i] == ','){
  • res.push_back(s);
  • s = "";
  • }
  • else
  • s += preorder[i];
  • }
  • res.push_back(s);
  • for(int i = 0; i < res.size(); i++){
  • if(res[i] == "#")
  • count--;
  • else{
  • if(i == 0)
  • count = 2;
  • else
  • count++;
  • }
  • if((count == 0) && (i < res.size()-1)) return false;
  • }
  • if(count == 0) return true;
  • else return false;
  • }
  • };


    • 2.别人的代码  精炼

    1.  bool isValidSerialization(string preorder) {
    2.         if(preorder.empty())return false;
    3.         int cnt=1,i=0;
    4.         while(i<preorder.size()){
    5.             if(preorder[i]=='#')cnt--;
    6.             else cnt++;
    7.             if(cnt==0)break;
    8.             while(i<preorder.size()&&preorder[i++]!=',');
    9.         }
    10.         return cnt==0&&i==preorder.size()-1;
    11.     }




    543. Diameter of Binary Tree

    543. Diameter of Binary Tree

    /**
 * DeFinition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 * };
 */
class Solution {
public:
    int res = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        helper(root);
        return res;
    }
    int helper(TreeNode* root) {
        if (root == NULL)   return 0;
        int left = helper(root->left) + 1;
        int right = helper(root->right) + 1;
        res = max(res,left+right-2);
        return max(left,right);
    }
};

    543.Diameter of Binary Tree

    543.Diameter of Binary Tree

    Given a binary tree,you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

    Example:
    Given a binary tree 

              1
         /         2   3
       / \     
      4   5

    Return 3,which is the length of the path [4,2,1,3] or [5,3].

    Note: The length of path between two nodes is represented by the number of edges between them.

    思路：其实所谓的二叉树的“直径”其实就是节点左右子树的最大深度和，而现在需要求出这个和的最大值。在递归求二叉树的深度时，记录下当前每个节点的深度，比较出最大值即可。

     1 /**
 2  * DeFinition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int diameterOfBinaryTree(TreeNode* root) 
13     {
14       res = 1;
15       treeDepth(root);
16       return res - 1;
17     }
18     int treeDepth(TreeNode* node)
19     {
20       if(node == nullptr)
21         return 0;
22       int L = treeDepth(node->left);
23       int R = treeDepth(node->right);
24       res = max(res,L+R+1);
25       return max(L,R)+1;
26     }
27   private:
28   int res;
29 };

    关于Diameter of Binary Tree的问题就给大家分享到这里，感谢你花时间阅读本站内容，更多关于173. Binary Search Tree Iterator - Medium、331. Verify Preorder Serialization of a Binary Tree、543. Diameter of Binary Tree、543.Diameter of Binary Tree等相关知识的信息别忘了在本站进行查找喔。

    本文标签：

    上一篇Miller_Rabin素性测试（miller-rabin素性测试）

    下一篇Searching for MobileNetV3

    相关文章