画出含11个节点的二叉树深度和节点为4写出前序遍历结果

来源：蜘蛛抓取(WebSpider) 时间：2019-12-18 09:48 标签： 二叉树深度和节点

给定一个前序序列数组构造一个二叉树

思路：首先序列中要囿给定的非法值也就是二叉树中对应的空节点；对于构造一个二叉树可以使用递归的思想：先构造当前节点，再构造左子树再右子树，直到遇到非法值时将NULL返回，使得上一个节点的一端链接到NULL图示如下：

前、中、后序遍历递归写法：

前序遍历：先遍历根节点，再遍历左子树再遍历右子树；所以最先输出根節点；
中序遍历：先遍历根节点左子树，再遍历根节点再遍历右子树；
后序遍历：先遍历左子树，再右子树最后根节点。
输出结果：拿一开始构造的二叉树为例

前、中、后序遍历非递归写法：

思路：将递归转递归无非就是转为循环或者使用栈来模拟递归的过程；前序和后序比较简单在后序遍历时需要注意加判断当前節点的右子树是否已经遍历过，只有当左右子树都遍历过后才可输出当前根节点。

思路一：利用子问题的思想：左子树节点个数加右子树节点个数加自己的一个如果当前节点为NULL，则返回0；
思路二：利用遍历的思想：给定一个参数遍历所有节点，只要不为NULL节点个数加1

求叶子节点数目：如同求节点数目，只不过在统计数目时需要判断是否左右都为NULL所以也可分为两种写法：

思路一：子问题：左子树叶子节点个数加右子树叶子节点个数，同时还要注意如果只有一个节点
思路二：遍历思想，只有当当前节点为叶子节点时才对计数+1；切记size要传引用，否则回到第一个栈帧时size仍为0！

思路：需要注意的是高度是最长的那条路；划分为子问題为：该节点的高度等于左子树和右子树高度中大的那个再加上1。 
 
 
 


  

  
 

 
 
 

  

  
 

  

    

    

      思蕗：利用队列先进先出的特性完成
    

  

  



                            

                                                    

                                

  

    

      

        
          

            
          

          

            
          

        
      

      

        
          
          
        
        
          

            
            
              

                不是 2个根本不是同一个概念
              

            		
          

          

            
          

        
      

      

        
          
          
        
        
          

            
            
              

                前序遍历是深度优先遍历的一种

                但二叉树深度和节点优先遍历还包括中序遍历、后续遍历。
              

            		
          

          

            
          

        
      

      

        
          
          
        
        
          

            
            
              

                 我是不是可以这样理解.

                 如果说:写一个二叉树深度囷节点优先遍历的函数.是不是用中序遍历、后续遍历,前序遍历都符合题目要求?

              

            		
          

          

            
          

        
      

      

        
          
          
        
        
          

            
          

          

            
          

        
      

      

        
          
          
        
        
          

            
            
              

                

                  

                    前序遍历是深度优先遍历的一种

                    但二叉树深度和节点优先遍历还包括中序遍历、后续遍历。
                  

                

              

            		
          

        
      

    

    

      

        发布了8 篇原创文章 · 获赞 22 · 访问量 48万+
      

    

  



                            

                                                    

                                

  版权声明：本文为博主原创文章遵循 版权协议，转载请附上原文出处链接和本声明




  

    

      

        一.使用c++进行前中后遍历，层次和深度遍历（非递归）
      

      
 
 

    

    

      

        发布了19 篇原创文章 · 获赞 25 · 访問量 4万+
      

    

  



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 二叉树深度和节点 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐