Java 求解找树左下角的值

水深无声 2022-10-16 00:56 157阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、迭代分析
     *  三、递归分析
     *  四、总结

## 一、题目 ##

给定一个二叉树，在树的最后一行找到最左边的值  
![在这里插入图片描述][20210526104510331.png]

## 二、迭代分析 ##

该题用层序遍历更为简单，只需要一个标志位，每次记录每一层最左边的值即可

这样最后一次赋的值，就为最后一层最左边的值

class Solution { 
        public int findBottomLeftValue(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            Deque<TreeNode> deque = new LinkedList<>();
            deque.add(root);
            int size;
            int res = 0;
            TreeNode node;
            while (!deque.isEmpty()) { 
                size = deque.size();
                //flag用来标志每一层的第一个节点
                boolean flag = true;
                while (size > 0) { 
                    size--;
                    node = deque.poll();
                    //res记录每一层的第一个数字
                    if (flag) { 
                        res = node.val;
                        flag = false;
                    }
                    if (node.left != null) { 
                        deque.add(node.left);
                    }
                    if (node.right != null) { 
                        deque.add(node.right);
                    }
                }
            }
            return res;
        }
    }

## 三、递归分析 ##

该题也可以使用递归解决

树左下角的值，只需要找到最后一层，然后记录最后一层最左边的值即可

采用先序遍历实现，类似：[二叉树的所有路径][Link 1]

递归包含着回溯的思想

class Solution { 
        //记录最大的层树
        int maxLen = Integer.MIN_VALUE;
        //记录结果值
        int res = 0;
    
        public int findBottomLeftValue(TreeNode root) { 
            //初始0层
            traversal(root, 0);
            return res;
        }
    
        public void traversal(TreeNode root, int leftLen) { 
            if (root.left == null && root.right == null) { 
                if (leftLen > maxLen) { 
                    maxLen = leftLen;
                    res = root.val;
                }
                return;
            }
            if (root.left != null) { 
                traversal(root.left, leftLen + 1);
            }
            if (root.right != null) { 
                traversal(root.right, leftLen + 1);
            }
        }
    }

## 四、总结 ##

该题使用迭代法更为简单

递归法，也需要记住这种思想

[20210526104510331.png]: /images/20221014/fc34a370fc904648b611d6f707e925fb.png
[Link 1]: https://blog.csdn.net/nanhuaibeian/article/details/117219485