543. Diameter of Binary Tree

25-02-06 17

在本文中，我们将为您详细介绍543.DiameterofBinaryTree的相关知识，此外，我们还会提供一些关于154.MinimumDepthofBinaryTree、173.BinarySear

在本文中，我们将为您详细介绍543. Diameter of Binary Tree的相关知识，此外，我们还会提供一些关于154.Minimum Depth of Binary Tree、173. Binary Search Tree Iterator - Medium、543.Diameter of Binary Tree、545. Boundary of Binary Tree的有用信息。

本文目录一览：

543. Diameter of Binary Tree
154.Minimum Depth of Binary Tree
173. Binary Search Tree Iterator - Medium
543.Diameter of Binary Tree
545. Boundary 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);
    }
};

154.Minimum Depth of Binary Tree

题目：

Given a binary tree,find its minimum depth.

给定二叉树，找到它的最小深度。

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

最小深度是沿从根节点到最近的叶节点的最短路径上的节点数。

Note: A leaf is a node with no children.

注意：叶子是没有子节点的节点。

Example:

Given binary tree [3,9,20,null,15,7],

    3
   /   9  20
    /     15   7

return its minimum depth = 2.

解答：

 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 minDepth(TreeNode root) {
12         if(root==null) return 0;
13         int left=minDepth(root.left);
14         int right=minDepth(root.right);
15         return (left==0 || right==0) ? left+right+1:Math.min(left,right)+1;
16     }
17 }

详解：

DFS 栈递归

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();
 */

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 };

545. Boundary of Binary Tree

545. Boundary of Binary Tree

Still wrong result 

class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
      List<Integer> result = new ArrayList<>();
      if(root == null){
        return result;
      }
      
      if(root.left == null || root.right == null) result.add(root.val);
      leftbound(root.left,result);
      leaves(root,result);
      rightbound(root,result);
      result.remove(result.size() - 1);
      return result;  
    }
    private void leftbound(TreeNode root,List<Integer> result){
      if(root == null || (root.left == null && root.right == null)){
        return;
      }
      result.add(root.val);
      if(root.left == null){
        leftbound(root.right,result);
      }else{
        leftbound(root.left,result);
      }
    }
    
    private void rightbound(TreeNode root,List<Integer> result){
      Deque<Integer> stack = new LinkedList<>();
      if(root == null || (root.left == null  && root.right == null)){
        return;
      }
      stack.push(root.val);
      if(root.right == null){
        rightbound(root.left,result);
      }else{
        rightbound(root.right,result);
      }
      int size = stack.size();
      for(int i = 0; i < size; i++){
          int cur = stack.pop();
          result.add(cur);
      }
    }
    
    private void leaves(TreeNode root,List<Integer> result){
      if(root == null) return;
      if(root.left == null && root.right == null) result.add(root.val);
      leaves(root.left,result);
      leaves(root.right,result);
    }
}

今天关于543. Diameter of Binary Tree的介绍到此结束，谢谢您的阅读，有关154.Minimum Depth of Binary Tree、173. Binary Search Tree Iterator - Medium、543.Diameter of Binary Tree、545. Boundary of Binary Tree等更多相关知识的信息可以在本站进行查询。

本文标签：