获取二叉树的高度

问题分析

二叉树的高度是二叉树结点层次的最大值，也就是其左右子树的最大高度+1。
所以，可以用使用后续遍历解决问题。
当树为空时，高度为0；否则为其左右子树最大高度+1;

算法实现

TreeNode

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tree
{
    class TreeNode<T>
    {
        T data;
        TreeNode<T> LChrild;
        TreeNode<T> RChirld;
        
        public T Data { get => data; set => data = value; }
        internal TreeNode<T> LChrild1 { get => LChrild; set => LChrild = value; }
        internal TreeNode<T> RChirld1 { get => RChirld; set => RChirld = value; }

        public TreeNode(T data)
        {
            this.Data = data;
        }
        public TreeNode()
        {
            this.Data = default(T);
            this.LChrild1 = null;
            this.RChirld1 = null;
        }
    }
}

Program

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tree
{
    class Program
    {
        static int total = 0; //叶子结点数目

        static void Main(string[] args)
        {
            TreeNode<string> A = new TreeNode<string>("a");
            TreeNode<string> B = new TreeNode<string>("b");
            TreeNode<string> C = new TreeNode<string>("c");
            TreeNode<string> D = new TreeNode<string>("d");
            TreeNode<string> E = new TreeNode<string>("e");
            TreeNode<string> F = new TreeNode<string>("f");
            TreeNode<string> G = new TreeNode<string>("g");
            TreeNode<string> H = new TreeNode<string>("h");

            A.LChrild1 = B;
            B.RChirld1 = D;
            A.RChirld1 = C;
            D.LChrild1 = F;
            D.RChirld1 = G;
            C.RChirld1 = E;
            E.RChirld1 = H;

            Console.WriteLine(GetDepth(A));
        }

        /// <summary>
        /// 获取二叉树的高度
        /// </summary>
        /// <param name="node"></param>
        static int GetDepth(TreeNode<string> node)
        {
            int hl = 0;
            int hr = hl;
            int max = hr;

            if (node != null)
            {
                hl = GetDepth(node.LChrild1);   //左子树高度
                hr = GetDepth(node.RChirld1);   //右子树高度
                max = hl > hr ? hl : hr;    //取最大值
                return max + 1; //高度+1
            }
            else return 0;
        }
    }
}

思考

换一种思路，也可以使用先序遍历实现。
二叉树的高度（深度）为二叉树中结点层次的最大值。设根结点为第一层的
结点，所有 h 层的结点的左、右孩子结点在 h+1 层。故可以通过遍历计算二叉树 中的每个结点的层次，其中最大值即为二叉树的高度。

参考实现

由于这种实现需要设置全局变量，会提高耦合度。故这里只给出C++的参考实现。

void PreTreeDepth(BiTeee bt, int h) 
/* 先序遍历求二叉树 bt 高度的递归算法，h 为 bt 指向结点所在层次，初值 为 1*/
/*depth 为当前求得的最大层次，为全局变量，调用前初值为 0 */ {
    if(bt!=NULL) {
        if(h>depth) depth = h; 的值*/
        PreTreeDepth(bt->Lchild, h+1); /* 遍历左子树 */ 
        PreTreeDepth(bt->Rchild, h+1); /* 遍历右子树 */
    }
}

更简洁的实现

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
/// <summary>
/// 题目获取二叉树的高度
/// </summary>
namespace algorithm
{
    class Tree<T>
    {
        public T data;
        public Tree<T> left;
        public Tree<T> right;
    }

    class Program
    {
        static void Main(string[] args)
        {
            Tree<string> root = new Tree<string>()
            {
                data = "A",
                left = new Tree<string>()
                {
                    data = "B",
                    left = new Tree<string>()
                    {
                        data = "C",
                    },
                    right = new Tree<string>()
                    {
                        data = "D",
                        left = new Tree<string>() { data = "E"}
                    }
                }
            };

            Console.WriteLine(GetHeight(root));
        }

        static int GetHeight(Tree<string> root)
        {
            if (root == null) return 0;
            return Math.Max(GetHeight(root.left), GetHeight(root.right)) + 1;
        }
    }
}