Deepest left leaf node in a binary tree

Recursion

selfcontained recursionglobal variables outside of recursion

---

Recursion Design 

Whenever reach to a qualified node, record the node reference and level for that nodeif meet next qualified node, compare the level, if larger, refresh the global node reference and level.Recursively do 1 and 2 recursively for left tree and right tree

 

---

Data Structure 

public class AVLTreeNode { public int data { get; set; } public AVLTreeNode leftChild { get; set; } public AVLTreeNode rightChild { get; set; } public int height { get; set; } public AVLTreeNode(int data) { this.data = data; this.height = 1; } }

---

Source Code

public class Result { public int MaxHight { get; set; } public AVLTreeNode ResultNode { get; set; } } // Find deepest left node public void FindDeepestLeftNode(AVLTreeNode node, bool isLeft, int height, Result result) { if (node == null) { return; } if (isLeft) { if (node.leftChild == null && node.rightChild == null && height > result.MaxHight) { result.ResultNode = node; result.MaxHight = height; } } FindDeepestLeftNode(node.leftChild, true, height + 1, result); FindDeepestLeftNode(node.rightChild, false, height + 1, result); } public AVLTreeNode GetDeepestLeftNode() { Result result = new Result() { MaxHight = 0, ResultNode = null }; FindDeepestLeftNode(root, true, 0, result); return result.ResultNode; }

Complexity

Time complexity is O(N)

Space complexity is O(N)

转载于:https://www.cnblogs.com/xuyanran/p/8456150.html

相关资源：JAVA上百实例源码以及开源项目